Find Peak Element

Problem

A peak is an element strictly greater than both of its neighbors. Given an integer array nums where no two adjacent elements are equal, return the index of any peak. Treat the positions just outside the array as negative infinity, so the ends only need to beat their single inside neighbor.

Your algorithm must run in O(log n) time, even though the array is not sorted.

Examples

• Input: nums = [1, 2, 3, 1] → Output: 2 (3 is greater than both neighbors 2 and 1.)
• Input: nums = [1, 2, 1, 3, 5, 6, 4] → Output: 5 (or 1) (Both index 1 (value 2) and index 5 (value 6) are peaks; either is accepted.)
• Input: nums = [5] → Output: 0 (A single element beats its two imaginary −∞ neighbors.)

Constraints

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for every adjacent pair.
• Required time complexity: O(log n).

Think about it first

TL;DR

Binary search on the slope (climb toward the rising side) — O(log n) time, O(1) space.

Approach 1 — Brute force (scan for a peak)

Check each element against its neighbors; with −∞ beyond the ends, the first index where the sequence stops rising is a peak.

def findPeakElement(nums: list[int]) -> int:
    n = len(nums)
    for i in range(n):
        left_ok = i == 0 or nums[i - 1] < nums[i]
        right_ok = i == n - 1 or nums[i] > nums[i + 1]
        if left_ok and right_ok:
            return i
    return -1  # unreachable: a peak always exists

The first i with nums[i] > nums[i + 1] (or the last index) is always a peak, so one forward pass suffices. Time O(n), space O(1). This works at n <= 1000, but the problem requires O(log n), so we need a way to halve an unsorted array.

Approach 2 — Iterative binary search on the slope

The insight: a peak is guaranteed to exist on the uphill side of any element. If nums[mid] < nums[mid + 1], look to the right: either the values rise all the way to the last element (a peak, since beyond it is −∞) or they stop rising somewhere, and that turning point is a peak. Symmetrically, if nums[mid] > nums[mid + 1], a peak exists at mid or to its left. So one comparison of mid with its right neighbor discards half the array. The invariant is that the interval [lo, hi] always contains a peak, and no sortedness is required.

def findPeakElement(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1      # uphill to the right: peak lives there
        else:
            hi = mid          # falling here: mid or left holds a peak
    return lo

Walkthrough on nums = [1, 2, 1, 3, 5, 6, 4]:

1. lo=0, hi=6 → mid=3, nums[3]=3 < nums[4]=5 → lo=4.
2. lo=4, hi=6 → mid=5, nums[5]=6 > nums[6]=4 → hi=5.
3. lo=4, hi=5 → mid=4, nums[4]=5 < nums[5]=6 → lo=5.
4. lo == hi == 5 → return 5, and nums[5]=6 is indeed a peak. Note mid + 1 is always in range because lo < hi guarantees mid < hi. Time O(log n), space O(1).

Approach 3 — Recursive binary search

The insight: the invariant “this interval contains a peak” recurses cleanly: look at the middle, commit to the uphill half, and repeat until one element remains. This is the classic divide-and-conquer formulation of peak finding.

def findPeakElement(nums: list[int]) -> int:
    def go(lo: int, hi: int) -> int:
        if lo == hi:
            return lo
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            return go(mid + 1, hi)
        return go(lo, mid)

    return go(0, len(nums) - 1)

Walkthrough on nums = [1, 2, 3, 1]:

1. go(0, 3): mid=1, nums[1]=2 < nums[2]=3 → go(2, 3).
2. go(2, 3): mid=2, nums[2]=3 > nums[3]=1 → go(2, 2).
3. go(2, 2): lo == hi → return 2. Time O(log n), space O(log n) recursion stack — same comparisons as Approach 2, worth knowing as the textbook phrasing.

Common pitfalls

• Trying to verify “is mid a peak” with both neighbors and handling four cases — comparing only mid vs mid + 1 is enough and needs no boundary special-casing (the lo < hi condition keeps mid + 1 valid).
• Using hi = mid - 1 on the falling branch: when nums[mid] > nums[mid + 1], mid itself may be the peak; stepping past it can converge on a non-peak.
• Assuming the array must first be sorted or unimodal — the guarantee that adjacent elements differ plus the −∞ borders is all the structure needed, and any peak is accepted.
• Overthinking multiple peaks: the algorithm finds a peak, not the global maximum. Returning the max element’s index costs O(n) and is exactly the trap.

Pattern takeaway

Binary search generalizes beyond sorted arrays. It works whenever you can maintain an invariant (“the answer exists in [lo, hi]”) and make one local comparison that shrinks the interval while preserving that invariant. Here the local slope points toward a guaranteed peak. When a problem allows O(log n) on unsorted data, look for a local test that eliminates half the search space.