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.
Updated Medium read: 7 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Binary search on the slope | O(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 iTime 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
iis on the way up. The peak is strictly to the right ofi. - The next value is smaller. Index
iis the peak, or is on the way down. The peak is atior 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 loThis 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])); // 4Python
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])) # 4The comment after each line is the result you should see.
Common mistakes
- Using
hi = mid - 1on the falling branch. When the slope falls atmid,midmay be the peak itself. Removing it from the range returns a neighbour of the peak instead. - Using
lo = midon the rising branch. With a two-element range and the middle rounded down,midequalslo, 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. Herehi = midleaves a one-element range unchanged, so the loop would not end. - Comparing with the left neighbour.
heights[mid - 1]is out of range whenmidis 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