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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Find Peak Element and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →