DSA Finding a Peak Element

The problem

Find a Peak Element asks for a value that is greater than both of its neighbours. A list can hold several peaks, and any one of them is a correct answer.

An edge value has one neighbour, and it only needs to beat that one. Neighbouring values in this article are never equal. The answer below is given as the peak value with its index.

cases = [
    ([1, 3, 5, 4, 2], 5, 2),
    ([1, 2, 3, 1], 3, 2),
    ([5, 4, 3], 5, 0),
    ([1, 2], 2, 1),
    ([7], 7, 0),
]
for nums, peak, index in cases:
    print("nums", nums, "peak:", peak, "at index", index)

Read one row at a time. The third row peaks at its first value, which beats its only neighbour. The last row holds one value, and a lone value is a peak.

Intuition: an inside-only scan misses the edges

The first idea scans the inside values and tests each one against both neighbours. That finds most peaks. It silently misses a peak sitting on an edge, because an edge value never gets tested.

The row below climbs all the way to its last value. The inside scan finds no peak at all. The last value is a peak, and the scan's blind spot hides it.

nums = [1, 2, 3, 5]
found = None
for i in range(1, len(nums) - 1):
    if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
        found = nums[i]
print("inside scan found:", found)
print("last value beats its only neighbour:", nums[-1] > nums[-2])

A correct method must treat the edges as candidates from the start. The halving method below does that by never excluding an edge from its range. Rising ground is a promise, and the method follows it.

Brute force: test every value, edges included

The brute force tests every index in order. An inside value must beat both neighbours. An edge value must beat its one neighbour, and the first value that passes is returned.

def find_peak_brute(nums):
    tested = 0
    for i in range(len(nums)):
        tested += 1
        left_ok = i == 0 or nums[i] > nums[i - 1]
        right_ok = i == len(nums) - 1 or nums[i] > nums[i + 1]
        if left_ok and right_ok:
            return i, tested
    return -1, tested

for nums in [[1, 3, 5, 4, 2], [1, 2, 3, 5], [5, 4, 3]]:
    index, tested = find_peak_brute(nums)
    print("nums", nums, "peak:", nums[index], "at index", index, "values tested:", tested)

The scan is correct on every row, edges included. Its cost is position luck. A peak at the far end of a long list pays for nearly the whole list.

The optimal solution: always move uphill

Moving from any value toward a higher neighbour always leads to some peak, so the search compares the middle value with its right neighbour and keeps the uphill side. That one sentence is the whole method.

A middle value below its right neighbour means a peak sits on the right, because the rising ground must top out or reach the edge. A middle value above its right neighbour is itself a peak or has one on its left, so the right edge moves to the middle.

def find_peak(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

cases = [
    ([1, 3, 5, 4, 2], 5, 2),
    ([1, 2, 3, 1], 3, 2),
    ([5, 4, 3], 5, 0),
    ([1, 2], 2, 1),
    ([7], 7, 0),
]
for nums, peak, index in cases:
    result = find_peak(nums)
    print("nums", nums, "-> peak", nums[result], "at index", result, "expected:", peak, "at", index, "match:", result == index)

All five cases from the start of the article pass. The edge rows pass with the same two moves as the inside rows. No edge needs a special rule, because the range never excludes an edge before it closes.

Walkthrough: climbing to 7

The walk halves one range. The state is the two edges and the middle value beside its right neighbour. Each step keeps the uphill side.

nums = [1, 3, 5, 7, 6, 4, 2]
lo = 0
hi = len(nums) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] < nums[mid + 1]:
        print("range", lo, hi, "- mid value", nums[mid], "next", nums[mid + 1], "- move: right, uphill")
        lo = mid + 1
    else:
        print("range", lo, hi, "- mid value", nums[mid], "next", nums[mid + 1], "- move: left, mid may be the peak")
        hi = mid
print("peak:", nums[lo], "at index", lo)

The range closes on 7 at index 3. Its neighbours are 5 and 6, and 7 beats both. The answer is read straight off the final range.

Complexity

The full scan tests up to n values, so its time is O(n). The uphill search halves its range on every step, so its time is O(log n).

Both methods store only a few index values. Their extra space is O(1).

def find_peak_steps(nums):
    lo = 0
    hi = len(nums) - 1
    steps = 0
    while lo < hi:
        mid = (lo + hi) // 2
        steps += 1
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo, steps

for n in [7, 15, 31]:
    nums = list(range(1, n)) + [0]
    index, steps = find_peak_steps(nums)
    print("values", n, "- scan worst case:", n, " uphill steps:", steps, " peak:", nums[index])

Counts beat clocks here. At 31 values the scan can test all 31. The uphill search reaches the peak in 5 steps on a list that rises almost the whole way.

Edge cases and pitfalls

Moving the right edge to one before the middle is the classic bug. The middle value itself may be the peak when the ground falls to its right. Dropping it can return a value that is not a peak at all, as the run below shows.

Multiple peaks need no special handling. The method promises one peak, not the highest value. A returned value that beats its neighbours is a complete answer.

def find_peak_buggy(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

def find_peak(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

buggy = find_peak_buggy([1, 3, 2])
print("buggy version on [1, 3, 2]: value", [1, 3, 2][buggy], "at index", buggy)
print("correct version on [1, 3, 2]: index", find_peak([1, 3, 2]))
print("single value:", find_peak([7]))
print("two values rising:", find_peak([1, 2]))
print("two values falling:", find_peak([2, 1]))
print("peak at the first index:", find_peak([9, 5, 3, 1]))
print("peak at the last index:", find_peak([1, 3, 5, 9]))
print("one of several peaks:", find_peak([2, 5, 4, 3, 8, 9, 1]))

The buggy version returns index 0 on its test list, and the value 1 there beats neither neighbour. The correct version returns the peak at index 1. Edge peaks and later peaks all come from the same two edge moves.