Highest Point on the Ridge

MediumBinary Search

Problem

A hiking app records the altitude at evenly spaced points along a ridge trail as alt. The trail climbs strictly to a single summit and then descends strictly: alt[0] < alt[1] < ... < alt[p] > alt[p + 1] > ... > alt[n - 1], with 0 < p < n - 1.

Return p, the index of the summit, in O(log n) time.

Example 1

Input:
alt = [1, 4, 7, 3, 2]
Output:
2

The trail climbs to 7 and then descends.

Example 2

Input:
alt = [0, 10, 5]
Output:
1

Example 3

Input:
alt = [2, 3, 4, 5, 1]
Output:
3

Constraints

  • 3 ≤ alt.length ≤ 2 · 10^5
  • 0 ≤ alt[i] ≤ 10^6
  • alt strictly increases to one peak and then strictly decreases; the peak is not at either end.

Hint

Show the first hint

Standing at index mid, how can you tell whether you are on the way up or on the way down?

Walkthrough

How to approach it

01Clarify before coding

  • Is the climb strictly increasing? Yes, there are no flat stretches, so neighbours never tie.
  • Can the summit be at an end? No: 0 < p < n - 1.
  • Is there exactly one summit? Yes, one strict rise followed by one strict fall.

02Brute force

Scan for the index of the maximum value (or the first i with alt[i] > alt[i + 1]).

Cost: O(n) time, O(1) space; it never uses the shape of the trail.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.