Longest Ridge
MediumTwo Pointers
Problem
A hiking app stores trail elevations heights. A ridge is a contiguous stretch of at least three points that strictly climbs to a single peak and then strictly descends: h[i] < … < h[p] > … > h[j] with i < p < j.
Return the length of the longest ridge, or 0 if there is none.
Example 1
- Input:
- heights = [1, 4, 7, 3, 2, 5]
- Output:
- 5
[1, 4, 7, 3, 2] climbs to 7 and descends.
Example 2
- Input:
- heights = [3, 3, 3]
- Output:
- 0
Flat ground never forms a ridge.
Example 3
- Input:
- heights = [1, 2, 3, 4]
- Output:
- 0
It only climbs; there is no descent.
Constraints
- 1 ≤ heights.length ≤ 10^5
- 0 ≤ heights[i] ≤ 10^5
Hint
Show the first hint
Every ridge starts at a point where the trail begins to climb. Where does the next candidate start once one ridge ends?
Walkthrough
How to approach it
01Clarify before coding
- Do plateaus count? No, both slopes must be strict.
- Minimum length? Three points: up, peak, down.
- Can ridges share points? Yes, a valley can end one ridge and start the next.
02Brute force
For every peak candidate, expand left while strictly decreasing and right while strictly decreasing; or check every subarray.
Cost: Checking every subarray is O(n³); expanding from each peak is O(n²) in the worst case without care, O(n) with up/down arrays and O(n) memory.
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.
This problem is part of Pro.