The Lone Summit

Medium

A mountain trail profile is given as an array heights, measured at evenly spaced points. Neighbouring heights always differ. A summit is a point strictly higher than both of its neighbours. Beyond the ends of the profile there is a bottomless drop, so an end point only has to be higher than its single neighbour. The trail is guaranteed to have exactly one summit: it only climbs at first and then only descends (either part may be empty). Return the index of the summit (0-based). A linear scan is obvious; find the summit in O(log n).

Example 1

heights=[120, 340, 515, 470, 90] → 2

The trail climbs to 515 and only goes down after that. The summit is at index 2.

Example 2

heights=[900, 650, -20] → 0

The trail descends from the very start, so the first point (index 0) is the summit: anything beyond the edges counts as lower.

Example 3

heights=[-5, 1, 8, 30] → 3

Constraints

1 ≤ len(heights) ≤ 1000
-2³¹ ≤ heights[i] ≤ 2³¹ - 1
heights[i] ≠ heights[i + 1]
There is exactly one summit

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

Find in a Shifted Sorted Array Medium First and Last Copy Medium Find in a Row-Chained Grid Medium Find in a Shifted Array With Repeats Medium Minimum of a Shifted List Medium

Input

heights=[120, 340, 515, 470, 90]

Expected

Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.