Find Peak Element (LeetCode 162)

The problem

You get an integer array nums where no two neighbours are equal. A peak is an element strictly greater than its neighbours. Imagine nums[-1] and nums[n] are minus infinity, so the ends can be peaks too. Return the index of any peak, in O(log n) time.

Input:  [1, 2, 1, 3, 5, 6, 4]
Output: 5

6 at index 5 is bigger than 5 and 4. Index 1 (2) is also a peak, so 1 would be accepted too.

How to think about it

Start with brute force. Scan for the first i where nums[i] > nums[i+1]; that i is a peak (or the last index is). That is O(n). Simpler still is nums.index(max(nums)), also O(n). The problem asks for O(log n), and the array is not sorted, which is why this problem surprises people.

Binary search doesn’t need a sorted array. It needs a rule that tells you which half still contains an answer. Look at mid and its right neighbour.

The key insight: walk uphill and you must reach a peak. If nums[mid] < nums[mid+1], you are on a rising slope. Keep walking right: the values either keep rising until the end (and the last element is a peak, because nums[n] is minus infinity), or they drop at some point, and the top before the drop is a peak. Either way there is a peak to the right of mid, so lo = mid + 1. If nums[mid] > nums[mid+1], the same argument going left shows a peak exists at mid or to its left, so hi = mid. When lo == hi, you are standing on a peak.

Which pattern is this? Binary search on a local property, not a global order. The tell is “find any element with property X” plus O(log n) on unsorted data. The question to ask: “Given mid, can I prove one side definitely contains an answer?”

Approach

1. Set lo = 0, hi = len(nums) - 1.
2. While lo < hi:
   • mid = (lo + hi) // 2. Note mid < hi, so mid + 1 is always in range.
   • If nums[mid] < nums[mid+1], set lo = mid + 1 (uphill to the right).
   • Else set hi = mid (mid may be the peak).
3. Return lo.

Solution

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid+1]: lo = mid + 1   # rising: a peak lies to the right
        else: hi = mid                             # falling: peak at mid or left
    return lo
# find_peak([1,2,1,3,5,6,4]) -> 5  (index of a peak; 1 is also valid)

Dry run

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

Now lo == hi == 5, and nums[5] = 6 is a peak. The answer is 5.

Complexity

• Time: O(log n). Each step halves [lo, hi].
• Space: O(1).

Edge cases and pitfalls

• Single element: index 0 is a peak, and the loop never runs.
• Strictly increasing array: the answer is the last index. Strictly decreasing: index 0.
• Index out of range: comparing with nums[mid+1] is safe only because lo < hi guarantees mid < hi. Comparing with nums[mid-1] instead needs the opposite rounding.
• Equal neighbours would break the argument, which is why the problem forbids them.
• “Binary search needs sorted input” is the misconception this problem tests. It needs a way to discard half, nothing more.

Related problems

• Find Minimum in Rotated Sorted Array (LeetCode 153): the same lo < hi, hi = mid loop on a non-sorted array.
• Search in Rotated Sorted Array (LeetCode 33): another search where local comparisons decide the half.
• Koko Eating Bananas (LeetCode 875): binary search over something that isn’t an array at all.