AlgoMaster Logo

Find Peak Element

medium6 min readUpdated June 23, 2026

Understanding the Problem

We need to find any element in the array that is larger than both its neighbors. The boundaries are treated as negative infinity, so the first element only needs to be larger than the second, and the last element only needs to be larger than the second-to-last.

One detail matters: no two adjacent elements are equal (nums[i] != nums[i + 1]). There are no flat plateaus, so between any two consecutive positions the array is strictly going up or strictly going down. Combined with the negative infinity boundaries, this guarantees that at least one peak always exists.

Treat the array as a mountain range. The leftmost element sits above negative infinity, so the terrain rises at the left boundary. The rightmost element also sits above negative infinity, so the terrain falls at the right boundary. A region that rises must eventually come back down, or it reaches the end of the array, which also counts as a peak. So a peak always exists.

This leads to the property the optimal solution relies on: from any position, if the element to the right is larger, a peak must exist somewhere to the right. That lets binary search work even though the array isn't sorted.

Key Constraints:

  • 1 <= nums.length <= 1000 → With n up to 1000, even O(n^2) would pass easily. But the problem explicitly requires O(log n), so binary search is the intended approach.
  • nums[i] != nums[i + 1] → No adjacent duplicates. Binary search depends on this, because it guarantees that every comparison between neighbors yields a strict direction (up or down).
  • -2^31 <= nums[i] <= 2^31 - 1 → Full 32-bit integer range. This doesn't affect the algorithm, but avoid subtracting values to compare, as that can overflow.

Approach 1: Linear Scan

Intuition

Walk through the array from left to right and stop at the first element that is greater than its right neighbor. That element is a peak: the previous element was smaller, otherwise the scan would have stopped earlier, and the next element is smaller by the comparison that triggered the stop. Both neighbors are smaller, so the position is a local maximum. The negative infinity boundary covers index 0, so if the first element already exceeds the second, the scan returns it immediately.

If we reach the end without finding such a drop, the last element is the peak.

Algorithm

  1. Iterate through the array from index 0 to n - 2.
  2. If nums[i] > nums[i + 1], return i. The element at index i is a peak because the terrain was rising to get here and now it drops.
  3. If the loop finishes without returning, return n - 1. The array was strictly increasing, so the last element is the peak.

Example Walkthrough

1Start scan: i=0, check if nums[0] > nums[1]
0
1
i
1
2
2
1
3
3
4
5
5
6
6
4
1/4

Code

The linear scan is O(n) and doesn't meet the O(log n) requirement. Comparing nums[mid] with its neighbor reveals which half contains a peak, so binary search can discard half the array at each step.

Approach 2: Binary Search

Intuition

Binary search normally requires a sorted array. This problem allows it on an unsorted array because of the mountain range guarantee. At any position mid, the comparison with its right neighbor points toward a half that is guaranteed to contain a peak:

  • If nums[mid] < nums[mid + 1], the terrain is going uphill to the right. The array ends at negative infinity on the right, so the uphill must eventually come back down. A peak exists somewhere in the range [mid + 1, right].
  • If nums[mid] > nums[mid + 1], the terrain is going downhill to the right. The array starts at negative infinity on the left, so either mid itself is a peak or a peak lies to its left. Either way, a peak exists in the range [left, mid].

Each step discards the half that cannot contain the targeted peak. This is binary search with a different comparison than the usual "is the target here?"

The search converges when left == right. The single remaining element is a peak, because every step moved the range toward a half that was guaranteed to hold one.

Algorithm

  1. Set left = 0 and right = nums.length - 1.
  2. While left < right:
    • Compute mid = left + (right - left) / 2.
    • If nums[mid] < nums[mid + 1], a peak is to the right: set left = mid + 1.
    • Otherwise, a peak is at mid or to the left: set right = mid.
  3. Return left.

Example Walkthrough

1Initialize: left=0, right=6, search entire array
0
1
left
1
2
2
1
3
3
4
5
5
6
6
4
right
search range
1/6

Code