Problem 19 · Binary Search

Find Peak Element

MediumClassic DSA & systems

01Problem

Given an array where adjacent elements differ, return the index of any peak (strictly greater than its neighbours, with out-of-bounds treated as -infinity) in O(log n).

02Key insight

Binary search on slope: if nums[mid] < nums[mid+1] a peak must exist to the right (the climb must end), otherwise one exists at mid or to the left. The array need not be sorted.

03Solution

solution.pypython9 lines

def find_peak_element(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  # ascending: peak lies right
        else:
            hi = mid
    return lo

Try it first.

TimeO(log n)

SpaceO(1)

tests.py · 4 passing

tests.pypython4 lines

assert find_peak_element([1,2,3,1]) == 2
assert find_peak_element([1,2,1,3,5,6,4]) in (1, 5)
assert find_peak_element([1]) == 0
assert find_peak_element([3,2,1]) == 0

04Staff-level follow-up

2D peak finding in an m x n grid? Binary search on columns, take each column's max and compare with neighbours: O(m log n).