The top of a mountain array
A mountain array strictly increases to a single highest element and then strictly decreases:
there is an index p with 0 < p < n − 1 such that
a[0] < … < a[p] > … > a[n − 1]. Given a mountain array, return p in O(log n)
comparisons.
Examples
| Input | Output | Why |
|---|---|---|
a = [0, 1, 0] | 1 | |
a = [0, 10, 5, 2] | 1 | |
a = [1, 3, 5, 7, 9, 8] | 4 |
Constraints
- 3 ≤ n ≤ 10⁵
- 0 ≤ a[i] ≤ 10⁶
- a is a mountain array
Hints
Hint 1
Compare a[mid] with a[mid + 1]. What does each outcome say about where the peak is?
Hint 2
If a[mid] < a[mid + 1], mid is on the way up and the peak is to its right. If a[mid] > a[mid + 1], mid is the peak or on the way down.
Hint 3
So "a[i] > a[i + 1]" is false then true along the array, and the peak is the first index where it is true.
Where people lose marks
- Comparing a[mid] with a[mid − 1] and a[mid + 1] both, and then needing special cases at the ends.
- Letting hi start at n, so that mid can be n − 1 and a[mid + 1] is read past the end.
- Returning the peak value instead of its index.
Dry run on [2,4,7,11,16,22,19,13,8,3]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6lo0hi9
The peak is somewhere in [0, n − 1]. At each step, look at the slope between mid and mid + 1.
-
Step 2 / 6lo0mid4hi9
a[4] = 16 < a[5] = 22. Still climbing: the peak is to the right, lo = 5.
-
Step 3 / 6lo5mid7hi9
a[7] = 13 > a[8] = 8. Going down: the peak is 7 or to its left, hi = 7.
-
Step 4 / 6lo5mid6hi7
a[6] = 19 > a[7] = 13. Going down: the peak is 6 or to its left, hi = 6.
-
Step 5 / 6lo5mid5hi6
a[5] = 22 > a[6] = 19. Going down: the peak is 5 or to its left, hi = 5.
-
Step 6 / 6answer5
lo = hi = 5: a[5] = 22 is the top of the mountain.
How to think about it
The array is not sorted, so comparing values with a target means nothing. What the array does have is a slope at every point, and the slope switches once. Define the test
descending(i) = a[i] > a[i + 1]
It is false at every index before the peak (the array is still rising) and true at the peak and after it. The
peak is the first index where it is true, which is a lower-bound search over [0, n − 1]:
- If
a[mid] > a[mid + 1], the peak is atmidor to its left:hi = mid. - Otherwise
midis on the rising side:lo = mid + 1.
With hi starting at n − 1, every mid is below n − 1, so
a[mid + 1] always exists.
This is the question to ask of any binary search: is there a test that switches exactly once? Sortedness is one way to get such a test, and a single change of slope is another.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def peak_index(a):
lo, hi = 0, len(a) - 1 # the peak is in [lo, hi]
while lo < hi:
mid = (lo + hi) // 2 # mid < hi, so a[mid + 1] exists
if a[mid] > a[mid + 1]:
hi = mid # going down: the peak is mid or to the left
else:
lo = mid + 1 # still climbing
return lo#include <vector>
int solve(const std::vector<int>& a) {
int lo = 0, hi = (int)a.size() - 1; // the peak is in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // mid < hi, so a[mid + 1] exists
if (a[mid] > a[mid + 1]) hi = mid; // going down
else lo = mid + 1; // still climbing
}
return lo;
}class Solution {
public int peakIndex(int[] a) {
int lo = 0, hi = a.length - 1; // the peak is in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // mid < hi, so a[mid + 1] exists
if (a[mid] > a[mid + 1]) hi = mid; // going down
else lo = mid + 1; // still climbing
}
return lo;
}
}function peakIndex(a) {
let lo = 0, hi = a.length - 1; // the peak is in [lo, hi]
while (lo < hi) {
const mid = (lo + hi) >> 1; // mid < hi, so a[mid + 1] exists
if (a[mid] > a[mid + 1]) hi = mid; // going down
else lo = mid + 1; // still climbing
}
return lo;
}fn solve(a: &[i64]) -> i64 {
// the peak is the first index where the next element is smaller
let (mut lo, mut hi) = (0usize, a.len() - 1);
while lo < hi {
let mid = lo + (hi - lo) / 2; // mid < hi, so a[mid + 1] exists
if a[mid] > a[mid + 1] { hi = mid } else { lo = mid + 1 }
}
lo as i64
}import Data.Array
solve :: [Int] -> Int
solve xs = go 0 (n - 1)
where
n = length xs
a = listArray (0, n - 1) xs
-- the peak is in [lo, hi]; mid < hi, so a ! (mid + 1) exists
go lo hi
| lo >= hi = lo
| a ! mid > a ! (mid + 1) = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- An array with several local peaks, where any one will do: the same search finds one, because walking uphill must reach a peak before the edge.
- Find a target value in a mountain array: find the peak, then search the rising side and the falling side.
- A two-dimensional grid: binary search on the columns, taking the maximum of each middle column.
Next problems
The one value without a partner
Before the single value, pairs start at even indices; after it, at odd ones. That switch is what the search finds.
Open the problem → Hard25 minFind a value in a mountain array
Find the peak, then search the rising side in ascending order and the falling side in descending order. Left side first, for the smallest index.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
The one value without a partner
Before the single value, pairs start at even indices; after it, at odd ones. That switch is what the search finds.
Open the problem → Hard25 minFind a value in a mountain array
Find the peak, then search the rising side in ascending order and the falling side in descending order. Left side first, for the smallest index.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.