Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Peak Index in a Mountain Array

Find the index of the largest value in an array that rises and then falls, in O(log n), by comparing the middle element with its right-hand neighbour.

easyPattern: Peak Finding

Updated Medium read: 7 min read

Approaches at a glance

ApproachTimeSpace
Linear scanO(n)O(1)
Binary search on the slopeO(log n)O(1)

The problem

A mountain array is an array of at least three integers that climbs strictly to a single highest value and then drops strictly after it. The highest value is never the first or the last element, so there is always at least one step up and one step down.

Given a mountain array, return the index of its highest value: the peak. The solution should run in O(log n) time.

heights = [3, 8, 12, 17, 21, 16, 4]   →  4    (the value 21)
heights = [1, 6, 2]                   →  1    (the value 6)
heights = [2, 30, 25, 19, 10, 5]      →  1    (the value 30)

"Strictly" means no two neighbours are equal: every step is either up or down, never level.

Approach 1: linear scan

Start at the left and keep walking while the ground rises. The first index whose next value is smaller is the peak.

JavaScript

function peakIndexInMountainLinear(heights) {
  let i = 0;
  while (i + 1 < heights.length && heights[i] < heights[i + 1]) {
    i++;
  }
  return i;
}

Python

def peak_index_in_mountain_linear(heights):
    i = 0
    while i + 1 < len(heights) and heights[i] < heights[i + 1]:
        i += 1
    return i

Time O(n), space O(1). When the peak is near the right-hand end, almost every element is read. It is a fine answer when nothing faster is asked for, and it is the version to test the fast one against.

What one comparison tells you

Pick any index i other than the last and compare heights[i] with heights[i + 1]. In a mountain array there are only two possible outcomes:

[3, 8, 12, 17, 21, 16, 4]
 └── next is bigger ──┘ └ next is smaller ┘
     (rising slope)       (peak and falling slope)
  • The next value is bigger. Index i is on the way up. The peak is strictly to the right of i.
  • The next value is smaller. Index i is the peak, or is on the way down. The peak is at i or to its left.

Reading across the array, the answer to "is the next value bigger?" is yes, yes, yes, then no, no, no. It changes once and never changes back. Finding the place where a yes-or-no answer changes is exactly the job binary search does, and the peak is the first index that answers "no".

Approach 2: binary search on the slope

Keep a range lo to hi that is known to contain the peak. Look at the middle, ask which slope it is on, and drop the half that cannot contain the peak.

JavaScript

function peakIndexInMountain(heights) {
  let lo = 0;
  let hi = heights.length - 1;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (heights[mid] < heights[mid + 1]) {
      lo = mid + 1;   // rising: the peak is to the right of mid
    } else {
      hi = mid;       // falling: the peak is mid or to its left
    }
  }
  return lo;
}

Python

def peak_index_in_mountain(heights):
    lo = 0
    hi = len(heights) - 1
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if heights[mid] < heights[mid + 1]:
            lo = mid + 1   # rising: the peak is to the right of mid
        else:
            hi = mid       # falling: the peak is mid or to its left
    return lo

This is the first template from the peak finding pattern. It has the same skeleton as the lower-bound search in Search Insert Position: the loop runs while lo < hi, one branch moves lo past the middle, and the other keeps the middle with hi = mid. The only new part is the test, which compares two neighbours instead of comparing the middle with a target.

Walkthrough

heights = [3, 8, 12, 17, 21, 16, 4]:

lo hi mid heights[mid] heights[mid + 1] Slope Action
0 6 3 17 21 Rising lo = 4
4 6 5 16 4 Falling hi = 5
4 5 4 21 16 Falling hi = 4
4 4 lo equals hi Return 4

And a mountain whose peak is close to the left, heights = [2, 30, 25, 19, 10, 5]:

lo hi mid heights[mid] heights[mid + 1] Slope Action
0 5 2 25 19 Falling hi = 2
0 2 1 30 25 Falling hi = 1
0 1 0 2 30 Rising lo = 1
1 1 lo equals hi Return 1

Notice that the loop never checks "is this the peak?". It only narrows the range, and the peak is whatever is left when the range is one index wide.

Time O(log n): the range halves on every step. Space O(1).

Why mid + 1 never goes out of bounds

Inside the loop lo is less than hi, and the middle is rounded down, so mid is at least lo and strictly less than hi. That makes mid + 1 at most hi, which is a valid index.

The same reasoning explains why the comparison is with the right-hand neighbour and not the left-hand one. When the range holds two elements, mid equals lo. Reading heights[mid - 1] would then look outside the range, and when lo is 0, outside the array.

Comparing the approaches

Linear scan Binary search on the slope
Time O(n) O(log n)
Space O(1) O(1)
Elements read for 1,000,000 items Up to 1,000,000 About 40 (two per step, 20 steps)
Works if neighbours can be equal Stops at the first level step No: a level step hides the slope
Risk of bugs Very low Off-by-one errors in the bounds

For a small array the two are indistinguishable. The binary search matters when the array is large or when each read is expensive, as in Find in Mountain Array, where the number of reads is capped.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(peakIndexInMountain([3, 8, 12, 17, 21, 16, 4])); // 4
console.log(peakIndexInMountain([1, 6, 2])); // 1
console.log(peakIndexInMountain([2, 30, 25, 19, 10, 5])); // 1
console.log(peakIndexInMountainLinear([5, 7, 9, 11, 13, 6])); // 4

Python

print(peak_index_in_mountain([3, 8, 12, 17, 21, 16, 4]))  # 4
print(peak_index_in_mountain([1, 6, 2]))  # 1
print(peak_index_in_mountain([2, 30, 25, 19, 10, 5]))  # 1
print(peak_index_in_mountain_linear([5, 7, 9, 11, 13, 6]))  # 4

The comment after each line is the result you should see.

Common mistakes

  • Using hi = mid - 1 on the falling branch. When the slope falls at mid, mid may be the peak itself. Removing it from the range returns a neighbour of the peak instead.
  • Using lo = mid on the rising branch. With a two-element range and the middle rounded down, mid equals lo, nothing changes, and the loop runs for ever.
  • Looping while lo <= hi. That condition belongs to the exact-match template, where both branches skip the middle. Here hi = mid leaves a one-element range unchanged, so the loop would not end.
  • Comparing with the left neighbour. heights[mid - 1] is out of range when mid is 0.
  • Returning the value instead of the index. The question asks where the peak is, not how tall it is.
  • Sorting, or calling a "maximum" helper. Both find the largest value, but in O(n log n) or O(n) time, which misses the point of the exercise.

Next, try Find Peak Element, where the array may have several hills and the same code still works.

Original problem: LeetCode 852: Peak Index in a Mountain Array