AlgoMaster Logo

Find Peak Element

Last Updated: March 29, 2026

medium
4 min read

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.

A critical detail: no two adjacent elements are equal (nums[i] != nums[i + 1]). This means there are no flat plateaus. The array is always going up or going down between consecutive positions. Combined with the negative infinity boundaries, this guarantees that at least one peak always exists.

Think of the array as a mountain range. The leftmost element starts above negative infinity, so the terrain is "rising" at the left boundary. The rightmost element also sits above negative infinity, so the terrain "falls" at the right boundary. If the terrain rises somewhere, it must come back down eventually (or we reach the end, which counts as a peak). That means a peak must exist.

The key insight for the optimal solution is this: if you're standing at some position and the element to the right is larger, then a peak must exist somewhere to the right. This allows binary search to 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. This is essential for binary search to work, 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

The most natural approach: walk through the array and check each element to see if it's a peak. Since the array starts at negative infinity, if the first element is larger than the second, it's a peak. Otherwise, the sequence is rising. As we scan from left to right, the moment we find an element that is greater than its right neighbor, we've found a peak. Why? Because the previous element was smaller (or we wouldn't have kept scanning), and the next element is also smaller, so we're at a local maximum.

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 works but doesn't meet the O(log n) requirement. Since comparing nums[mid] with its neighbor tells us which half contains a peak, we can use binary search to eliminate half the array at each step.

Approach 2: Binary Search

Intuition

Binary search normally requires a sorted array. But this problem has a special property that makes binary search work even on an unsorted array: the "mountain range" guarantee.

Here's the key insight. Stand at any position mid and look at its right neighbor:

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

So at every step, we can confidently throw away half the search space. This is binary search, just with a different comparison than the usual "is the target here?"

The search converges when left == right. At that point, the single remaining element must be a peak, because we've been consistently moving toward a guaranteed peak the entire time.

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