Find Peak Element

Medium#162uphill

You get an array where no two neighbours are equal. A peak is a number bigger than its neighbours; past both ends there is −∞. Return the index of any peak in O(log n) time. Our example: [2, 5, 9, 4, 3, 6, 8, 1] — 9 at index 2 and 8 at index 6 are peaks; the run returns 2.

162 Find Peak ElementWalkthrough · 1×

Example: [2, 5, 9, 4, 3, 6, 8, 1] as bars. The arrow is the comparison of mid with its right neighbour.

2051924334658617lo
still in the rangemiddle, checked nowthrown awaya peak

lo starts at the first index, 0

01/16
restart · back · play · step
Speed
1function findPeakElement(nums):
2 lo = 0
3 hi = len(nums) - 1
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < nums[mid + 1]: // uphill
7 lo = mid + 1
8 else: // downhill: a peak at mid or before
9 hi = mid
10 return lo
state
lo
0
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Past the ends there is −∞, so walking uphill always reaches a peak: the slope cannot rise forever and has to turn down, at the latest past the end.
  2. If nums[mid] < nums[mid + 1], the slope rises to the right, and a peak is after mid. If not, it falls to the right: either mid is a peak or going left from it is uphill, so a peak is at mid or before it.
  3. Any peak is a valid answer, so dropping a half that also has one is fine. Here the first step drops the half with 8 and climbs to 9.

Complexity

Time O(log n): every step halves the range. Memory O(1): three indices.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.