Skip to main content

852. Peak Index in a Mountain Array

medium

Locate the peak of a strictly increasing-then-decreasing array in O(log n). A focused version of Find Peak Element that drills the 'compare with neighbor' trick.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

An array arr is a mountain if the following properties hold: arr.length >= 3, and there exists some i with 0 < i < arr.length - 1 such that arr[0] < arr[1] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[arr.length - 1]. Given a mountain array arr, return the index i such that arr[i] is the peak. You must solve it in O(log n) time.

Constraints

  • 3 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^6
  • arr is guaranteed to be a mountain array.

Examples

Example 1

Input
arr = [0,1,0]
Output
1

Example 2

Input
arr = [0,2,1,0]
Output
1

Example 3

Input
arr = [0,10,5,2]
Output
1

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

Even though the array isn't globally sorted, the strict monotonic structure on each side of the peak lets you binary-search.

Hint 2

Compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], you're on the ascending slope — peak is to the right.

Hint 3

Otherwise (arr[mid] > arr[mid + 1]), you're on the descending slope — peak is at mid or to the left.

Solution approach

Reveal approach

Binary search using neighbor comparison. Initialize lo = 0 and hi = n - 1. While lo < hi, compute mid = lo + (hi - lo) / 2. Compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], the peak must be to the right (mid is on the ascending slope), so lo = mid + 1. Otherwise arr[mid] > arr[mid + 1] (strict mountain — no ties) means mid is on the descending slope OR is the peak itself, so hi = mid. When lo == hi, that's the peak index. The invariant: the window always contains the peak. We never read arr[mid + 1] out of bounds because hi starts at n - 1 and we only compute mid + 1 when lo < hi, which forces mid < n - 1. O(log n) time, O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • modified-binary-search

Related problems

Asked at

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

  • Amazon
  • Google
  • Apple

Practice these live with InterviewChamp.AI

Drill Peak Index in a Mountain Array and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →