Skip to main content

162. Find Peak Element

medium

Find any peak element in an unsorted array in O(log n). The 'binary search where the array isn't sorted' surprise — interviewers love this one as a thinking test.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -infinity. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time.

Constraints

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums[i] != nums[i + 1] for all valid i.

Examples

Example 1

Input
nums = [1,2,3,1]
Output
2

Explanation: 3 is a peak element and your function should return the index number 2.

Example 2

Input
nums = [1,2,1,3,5,6,4]
Output
5

Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Linear scan is trivial but the problem demands O(log n). Surprising — array isn't sorted.

Hint 2

Key insight: compare nums[mid] to nums[mid + 1]. The smaller side is going downhill, but the other side must eventually rise then fall (with -INF sentinels at the ends) — so it contains a peak.

Hint 3

If nums[mid] < nums[mid + 1], a peak exists in (mid, hi]; set lo = mid + 1. Otherwise a peak exists in [lo, mid]; set hi = mid.

Hint 4

Half-open invariant (lo < hi). When they converge, lo points at a peak.

Solution approach

Reveal approach

Binary search on the 'uphill' direction. lo = 0, hi = n - 1. While lo < hi: mid = lo + (hi - lo) / 2. If nums[mid] < nums[mid + 1], we're climbing uphill — a peak must exist in (mid, hi] (with the +INF sentinel guaranteeing the climb stops), so lo = mid + 1. Otherwise we're going downhill or at a local peak — a peak exists in [lo, mid], so hi = mid. When lo == hi, return lo. O(log n) time, O(1) space. The invariant is 'the current window always contains a peak' — guaranteed by the -INF sentinels at both ends.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft

More Binary Search practice problems

See all Binary Search problems →