Logo

Kode$word

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)
Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

17 views
0
0
LeetCodeBinary SearchMediumJava
Github icon

Try the Question

Before reading the explanation, try solving the problem yourself:

👉 https://leetcode.com/problems/find-peak-element/

Attempting the problem first helps develop algorithmic intuition, especially for binary search problems.


Problem Statement

You are given a 0-indexed integer array nums.

Your task is to find the index of a peak element.

What is a Peak Element?

A peak element is an element that is strictly greater than its immediate neighbors.

For an element nums[i] to be a peak:

nums[i] > nums[i-1]
nums[i] > nums[i+1]

However, the array boundaries have a special rule.

Boundary Rule

You can imagine that:

nums[-1] = -∞
nums[n] = -∞

This means:

  1. The first element only needs to be greater than the second element.
  2. The last element only needs to be greater than the second last element.

Constraints

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
nums[i] != nums[i + 1] for all valid i

Important implications:

  1. Adjacent elements are never equal.
  2. The array always has at least one peak.


Understanding the Problem with Examples

Example 1

Input

nums = [1,2,3,1]

Visualization

1 2 3 1
^

Here:

3 > 2
3 > 1

So 3 is a peak element.

Output

2

(index of value 3)

Example 2

Input

nums = [1,2,1,3,5,6,4]

Visualization

1 2 1 3 5 6 4
^ ^

Possible peaks:

2
6

Valid outputs:

1 or 5

Either peak index is acceptable.


Key Observations

Important facts about peak elements:

  1. Every array must contain at least one peak.
  2. If numbers keep increasing, the last element will be a peak.
  3. If numbers keep decreasing, the first element will be a peak.
  4. If the array has ups and downs, peaks exist in the middle.

This guarantees a solution exists.


Approach 1 — Linear Scan (Brute Force)

The simplest approach is to check each element and see whether it satisfies the peak condition.

Algorithm

  1. Traverse the array.
  2. Check if the current element is greater than neighbors.
  3. Return the index if found.

Example

nums = [1,2,3,1]

Check:

1 < 2
2 < 3
3 > 2 and 3 > 1 → Peak

Implementation

public int findPeakElement(int[] nums) {

for(int i = 0; i < nums.length; i++){

boolean left = (i == 0) || nums[i] > nums[i-1];
boolean right = (i == nums.length-1) || nums[i] > nums[i+1];

if(left && right){
return i;
}
}

return -1;
}

Time Complexity

O(n)

Space Complexity

O(1)

Although simple, this solution does not satisfy the required O(log n) complexity.


Approach 2 — Binary Search Using Peak Conditions

Instead of scanning the entire array, we can use binary search.

Key Idea

If we are at index mid, compare it with the neighbors.

Three situations may occur.

Case 1 — Peak Found

nums[mid-1] < nums[mid] > nums[mid+1]

Then:

mid is the peak

Case 2 — Increasing Slope

nums[mid] < nums[mid+1]

Example:

1 3 5 7
^

This means the peak must exist on the right side.

Move search to the right.

Case 3 — Decreasing Slope

nums[mid] < nums[mid-1]

Example:

7 5 3 1
^

Peak exists on the left side.

Move search to the left.

Implementation

int i = 1;
int j = nums.length - 2;

while(i <= j){

int mid = i + (j - i)/2;

if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]){
return mid;
}
else if(nums[mid] < nums[mid+1]){
i = mid + 1;
}
else{
j = mid - 1;
}
}

Time Complexity

O(log n)

Space Complexity

O(1)

Approach 3 — Optimized Binary Search (Most Elegant Solution)

A simpler and more elegant version of binary search exists.

Core Intuition

Compare:

nums[mid]
nums[mid + 1]

Two possibilities exist.

Case 1 — Increasing Slope

nums[mid] < nums[mid+1]

Example:

1 2 3 4
^

The peak must exist on the right side.

Move:

left = mid + 1

Case 2 — Decreasing Slope

nums[mid] > nums[mid+1]

Example:

4 3 2 1
^

Peak exists on the left side including mid.

Move:

right = mid

This gradually narrows down to the peak.


Final Optimized Implementation

class Solution {

public int findPeakElement(int[] nums) {

int i = 0;
int j = nums.length - 1;

while(i < j){

int mid = i + (j - i) / 2;

if(nums[mid] < nums[mid + 1]){
i = mid + 1;
}else{
j = mid;
}
}

return i;
}
}


Step-by-Step Example

Array

[1,2,1,3,5,6,4]

Iteration 1

mid = 3
nums[mid] = 3
nums[mid+1] = 5

Increasing slope → move right.

Iteration 2

mid = 5
nums[mid] = 6
nums[mid+1] = 4

Decreasing slope → move left.

Eventually:

peak index = 5

Value:

6


Why This Binary Search Works

The array behaves like a mountain landscape.

Example visualization:

/\
/ \
/ \__

If you stand at mid:

  1. If the right side is higher, go right.
  2. If the left side is higher, go left.

This guarantees that you will eventually reach a peak.

Time Complexity

O(log n)

Each iteration cuts the search space in half.

Space Complexity

O(1)

Only a few variables are used.


Key Takeaways

✔ A peak element is greater than its neighbors

✔ The array always contains at least one peak

✔ Binary search can be applied using slope comparison

✔ The optimized solution only compares nums[mid] and nums[mid+1]

✔ The final algorithm runs in O(log n) time


Final Thoughts

This problem is an excellent example of applying binary search beyond sorted arrays.

Instead of searching for a value, binary search is used here to locate a structural property of the array (a peak).

Understanding this pattern is extremely valuable because similar logic appears in many interview problems involving:

  1. Mountain arrays
  2. Bitonic arrays
  3. Optimization search problems

Mastering this approach will significantly improve your binary search problem-solving skills for technical interviews.

Related Articles

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

Read Article
Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Learn how to efficiently search for an element in a rotated sorted array using binary search. This guide explains the intuition, multiple strategies, and a clean Java implementation that achieves O(log n) time complexity.

Read Article
Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Learn how to determine whether a binary string contains only one continuous group of 1s. This article explains the problem clearly, builds the intuition step-by-step, and walks through a clean Java solution with time complexity analysis.

Read Article

Ai Assistant Kas