Peak Index in a Mountain Array (LC 852)
You're given a mountain array arr of length n: its values climb up to one peak and then descend.
Return the index of that peak.
Solve it in O(log n) time.
Worked Examples
arr = [0,1,0]1arr = [0,2,1,0]1arr = [0,10,5,2]1⚖️Formal Constraints & Bounds
3 <= arr.length <= 1050 <= arr[i] <= 106arris guaranteed to be a mountain array.
Core Insight
Compare arr[mid] with arr[mid + 1]. If the values fall after mid, a peak is at mid or to its left (hi = mid). If they rise, a peak is to its right (lo = mid + 1). Even when the values are not sorted, this one comparison removes half of the candidates.
Real-World Scenario & Production Applications
Terrain navigation sensor processing, signal processing peak detection, and CPU frequency throttling curves.
Subproblems & Recurrence Decomposition3 Phases
Ask each index one yes-or-no question: do the values fall after i? That is arr[i] > arr[i + 1]. The check reads the next value, so the candidates are 0 to n - 2, and the range is [lo, hi) = [0, n - 1).
# Check: do the values fall after i?
def is_falling(i):
return arr[i] > arr[i + 1]
lo, hi = 0, n - 1Step-by-Step Execution Trace Table
| Step | Range [lo, hi) | mid | arr[mid] > arr[mid + 1]? | Decision | New range [lo, hi) |
|---|---|---|---|---|---|
| 1 | [0, 6) | 3 | 10 > 8 → True | The values fall after 3, so a peak is at 3 or to its left: hi = mid | [0, 3) |
| 2 | [0, 3) | 1 | 2 > 5 → False | The values rise after 1, so a peak is to its right: lo = mid + 1 | [2, 3) |
| 3 | [2, 3) | 2 | 5 > 10 → False | The values rise after 2, so a peak is to its right: lo = mid + 1 | [3, 3) |
| 4 | [3, 3) | The range is empty. Lower Bound returns 3, and arr[3] = 10 is the peak. |
The trace for arr = [0, 2, 5, 10, 8, 4, 1], step by step:
- The candidates are the indices
0to5, because the check reads the next value. Solo = 0andhi = 6. - Step 1 checks
mid = 3:arr[3] = 10andarr[4] = 8. The check is True, so a peak is at index 3 or to its left. We keep index 3 withhi = mid. - Step 2 checks
mid = 1:arr[1] = 2andarr[2] = 5. The check is False, so a peak is to the right. We skip index 1 withlo = mid + 1. - Step 3 checks
mid = 2:arr[2] = 5andarr[3] = 10. The check is False, solo = mid + 1 = 3. - Step 4:
lois equal tohi, so the range is empty. Lower Bound returns 3.
| 1 | def is_falling(i: int) -> bool: |
| 2 | return arr[i] > arr[i + 1] |
| 3 | lo = 0 |
| 4 | hi = n - 1 |
| 5 | return binary_search_lower_bound(lo, hi, is_falling) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Extrema Search compares a value with the value next to it, not with a target. The check asks one question about the slope: do the values fall after this index? If they fall, a peak is at this index or to its left. If they rise, a peak is to its right.
⛰️ The Analogy: Walking Uphill In The Dark
Imagine a path over a hill, and you cannot see the top. At any point, you can feel if the next step goes up or down. If the next step goes up, the top is ahead of you. If the next step goes down, you are on the top or you have passed it. You never need to know your height. You only need the direction of the next step.
🔑 Why It Works
The loop keeps one fact: a peak is always at an index from lo to hi. Lower Bound uses the check arr[i] > arr[i + 1]. When every check is False, the values rise to the end, so the last index is a peak. On a mountain, the check is False and then True, so the first True is the top. On a list with several peaks, the check is not False and then True, and the search still returns one peak, not the highest.
Setting
hi = nwhile the check readsarr[i + 1]Using the check when two neighbouring values can be equal
Returning the value instead of the index
In the grid, comparing a cell with its left and right neighbours at the same time
In the grid, comparing the first cell of the column instead of its largest cell
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Its values climb up to one peak and then descend. Return the index of that peak. Solve it in O(log n) time.": a rise-then-fall shape and a logarithmic budget point to Extrema Search.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a peak is always at an index from lo to hi. The check arr[i] > arr[i + 1] asks if the values fall after i. On a mountain, it is False and then True, so Lower Bound finds the first True, the top. On a list with several peaks, it is not False and then True, and the invariant still holds.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Setting
hi = nwhile the check readsarr[i + 1]: the last candidate reads past the end, and Python raises anIndexError(arr = [1, 2, 3]). The candidates are0ton - 2, sohi = n - 1.Expecting the highest peak: with several peaks the search returns one of them, and
arr = [3, 1, 2]returns index 2, not index 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is Extrema Search. I run Lower Bound with the check
arr[i] > arr[i + 1], which asks if the values fall afteri. If they fall, a peak is atior to its left, so Lower Bound keepsmid. If they rise, a peak is to its right, so Lower Bound skipsmid. The check reads the next value, so the candidates stop atn - 2, and I callbinary_search_lower_bound(0, n - 1, is_falling). When no candidate is True, the values rise to the end, and the last index is the peak. A peak is always betweenloandhi, so the search never loses it. The trap is expecting the highest peak: with several peaks, I return one of them. Each pass halves the range, so it isO(log n)time andO(1)space."
Complexity & Mathematical Proof
O(log N)
Look at the loop in Lower Bound: while lo < hi:. Each pass does one comparison, arr[mid] > arr[mid + 1], and keeps either [lo, mid) or [mid + 1, hi), which is at most half of the range. From N indices the loop runs at most ⌊log2 N⌋ + 1 times with O(1) work each: O(log N) time.
O(1)
Look at the memory used: the loop is iterative, so the call stack holds one frame. We store only the integers lo, hi and mid. Auxiliary space is O(1).
Derivation Progression
delta = arr[mid+1] - arr[mid]
If delta > 0, the values rise after mid, so a peak is to its right. Otherwise a peak is at mid or to its left.
lo = mid + 1 or hi = mid
A peak is always at an index from lo to hi, so removing the other part never loses it.
lo == hi ⟹ O(log N)
Converges on a peak in at most floor(log2 N) + 1 iterations.
Variable Definitions
Total number of elements in the mountain array
Memory Architecture & Bounds
O(1) Iterative
O(1) Scalar registers
O(1) Peak index integer
Boundary Best / Worst Cases
— Fixed binary search convergence.
.
— Every pass halves the range.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The statement describes a "mountain array" whose values "climb up to one peak and then descend", and asks for the peak's index "in O(log n) time". This is Extrema Search: nothing is compared with a target. The check arr[i] > arr[i + 1] asks if the values fall after i, and Lower Bound finds the first index where they do.
The array length is , with elements up to . The mountain property guarantees that the peak never resides at index or index . The check reads arr[i + 1], so the candidates are 0 to n - 2, and the search range is lo = 0 and hi = n - 1.
The card's trap is expecting the highest peak: with several peaks, the search returns one of them. A second trap is setting hi = n, which makes the last candidate read arr[n]. At scale there is one more: the data. With plateaus or equal neighbours the slope check is blind, so either confirm that neighbours differ or fall back to a linear scan. With noisy values, one comparison can point the wrong way, so compare smoothed values or wider gaps instead of single neighbours.
Peak Index in a Mountain Array (LC 852)
You're given a mountain array arr of length n: its values climb up to one peak and then descend.
Return the index of that peak.
Solve it in O(log n) time.
Worked Examples
arr = [0,1,0]1arr = [0,2,1,0]1arr = [0,10,5,2]1⚖️Formal Constraints & Bounds
3 <= arr.length <= 1050 <= arr[i] <= 106arris guaranteed to be a mountain array.
Core Insight
Compare arr[mid] with arr[mid + 1]. If the values fall after mid, a peak is at mid or to its left (hi = mid). If they rise, a peak is to its right (lo = mid + 1). Even when the values are not sorted, this one comparison removes half of the candidates.
Real-World Scenario & Production Applications
Terrain navigation sensor processing, signal processing peak detection, and CPU frequency throttling curves.
Subproblems & Recurrence Decomposition3 Phases
Ask each index one yes-or-no question: do the values fall after i? That is arr[i] > arr[i + 1]. The check reads the next value, so the candidates are 0 to n - 2, and the range is [lo, hi) = [0, n - 1).
# Check: do the values fall after i?
def is_falling(i):
return arr[i] > arr[i + 1]
lo, hi = 0, n - 1Step-by-Step Execution Trace Table
| Step | Range [lo, hi) | mid | arr[mid] > arr[mid + 1]? | Decision | New range [lo, hi) |
|---|---|---|---|---|---|
| 1 | [0, 6) | 3 | 10 > 8 → True | The values fall after 3, so a peak is at 3 or to its left: hi = mid | [0, 3) |
| 2 | [0, 3) | 1 | 2 > 5 → False | The values rise after 1, so a peak is to its right: lo = mid + 1 | [2, 3) |
| 3 | [2, 3) | 2 | 5 > 10 → False | The values rise after 2, so a peak is to its right: lo = mid + 1 | [3, 3) |
| 4 | [3, 3) | The range is empty. Lower Bound returns 3, and arr[3] = 10 is the peak. |
The trace for arr = [0, 2, 5, 10, 8, 4, 1], step by step:
- The candidates are the indices
0to5, because the check reads the next value. Solo = 0andhi = 6. - Step 1 checks
mid = 3:arr[3] = 10andarr[4] = 8. The check is True, so a peak is at index 3 or to its left. We keep index 3 withhi = mid. - Step 2 checks
mid = 1:arr[1] = 2andarr[2] = 5. The check is False, so a peak is to the right. We skip index 1 withlo = mid + 1. - Step 3 checks
mid = 2:arr[2] = 5andarr[3] = 10. The check is False, solo = mid + 1 = 3. - Step 4:
lois equal tohi, so the range is empty. Lower Bound returns 3.
| 1 | def is_falling(i: int) -> bool: |
| 2 | return arr[i] > arr[i + 1] |
| 3 | lo = 0 |
| 4 | hi = n - 1 |
| 5 | return binary_search_lower_bound(lo, hi, is_falling) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Extrema Search compares a value with the value next to it, not with a target. The check asks one question about the slope: do the values fall after this index? If they fall, a peak is at this index or to its left. If they rise, a peak is to its right.
⛰️ The Analogy: Walking Uphill In The Dark
Imagine a path over a hill, and you cannot see the top. At any point, you can feel if the next step goes up or down. If the next step goes up, the top is ahead of you. If the next step goes down, you are on the top or you have passed it. You never need to know your height. You only need the direction of the next step.
🔑 Why It Works
The loop keeps one fact: a peak is always at an index from lo to hi. Lower Bound uses the check arr[i] > arr[i + 1]. When every check is False, the values rise to the end, so the last index is a peak. On a mountain, the check is False and then True, so the first True is the top. On a list with several peaks, the check is not False and then True, and the search still returns one peak, not the highest.
Setting
hi = nwhile the check readsarr[i + 1]Using the check when two neighbouring values can be equal
Returning the value instead of the index
In the grid, comparing a cell with its left and right neighbours at the same time
In the grid, comparing the first cell of the column instead of its largest cell
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Its values climb up to one peak and then descend. Return the index of that peak. Solve it in O(log n) time.": a rise-then-fall shape and a logarithmic budget point to Extrema Search.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a peak is always at an index from lo to hi. The check arr[i] > arr[i + 1] asks if the values fall after i. On a mountain, it is False and then True, so Lower Bound finds the first True, the top. On a list with several peaks, it is not False and then True, and the invariant still holds.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Setting
hi = nwhile the check readsarr[i + 1]: the last candidate reads past the end, and Python raises anIndexError(arr = [1, 2, 3]). The candidates are0ton - 2, sohi = n - 1.Expecting the highest peak: with several peaks the search returns one of them, and
arr = [3, 1, 2]returns index 2, not index 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is Extrema Search. I run Lower Bound with the check
arr[i] > arr[i + 1], which asks if the values fall afteri. If they fall, a peak is atior to its left, so Lower Bound keepsmid. If they rise, a peak is to its right, so Lower Bound skipsmid. The check reads the next value, so the candidates stop atn - 2, and I callbinary_search_lower_bound(0, n - 1, is_falling). When no candidate is True, the values rise to the end, and the last index is the peak. A peak is always betweenloandhi, so the search never loses it. The trap is expecting the highest peak: with several peaks, I return one of them. Each pass halves the range, so it isO(log n)time andO(1)space."
Complexity & Mathematical Proof
O(log N)
Look at the loop in Lower Bound: while lo < hi:. Each pass does one comparison, arr[mid] > arr[mid + 1], and keeps either [lo, mid) or [mid + 1, hi), which is at most half of the range. From N indices the loop runs at most ⌊log2 N⌋ + 1 times with O(1) work each: O(log N) time.
O(1)
Look at the memory used: the loop is iterative, so the call stack holds one frame. We store only the integers lo, hi and mid. Auxiliary space is O(1).
Derivation Progression
delta = arr[mid+1] - arr[mid]
If delta > 0, the values rise after mid, so a peak is to its right. Otherwise a peak is at mid or to its left.
lo = mid + 1 or hi = mid
A peak is always at an index from lo to hi, so removing the other part never loses it.
lo == hi ⟹ O(log N)
Converges on a peak in at most floor(log2 N) + 1 iterations.
Variable Definitions
Total number of elements in the mountain array
Memory Architecture & Bounds
O(1) Iterative
O(1) Scalar registers
O(1) Peak index integer
Boundary Best / Worst Cases
— Fixed binary search convergence.
.
— Every pass halves the range.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The statement describes a "mountain array" whose values "climb up to one peak and then descend", and asks for the peak's index "in O(log n) time". This is Extrema Search: nothing is compared with a target. The check arr[i] > arr[i + 1] asks if the values fall after i, and Lower Bound finds the first index where they do.
The array length is , with elements up to . The mountain property guarantees that the peak never resides at index or index . The check reads arr[i + 1], so the candidates are 0 to n - 2, and the search range is lo = 0 and hi = n - 1.
The card's trap is expecting the highest peak: with several peaks, the search returns one of them. A second trap is setting hi = n, which makes the last candidate read arr[n]. At scale there is one more: the data. With plateaus or equal neighbours the slope check is blind, so either confirm that neighbours differ or fall back to a linear scan. With noisy values, one comparison can point the wrong way, so compare smoothed values or wider gaps instead of single neighbours.