Climb Detection with Recoverable Dips
Strava● MediumFULLTIMEPHONE SCREENProblem statement
Given an elevation sample array, return the first climb as [start, end], or an empty array when no climb exists.
A climb starts at the last sample of a valley plateau immediately before the first strict increase. Equal elevations are allowed during a climb. Its endpoint is the first index at which its final maximum elevation is reached.
After a maximum has been reached, a descent may be treated as a temporary dip only when every point in the dip loses at most 20% of the net gain from the climb start to that maximum and the elevation later becomes strictly greater than that maximum. Compare this threshold exactly as 5 * loss <= gain. Otherwise the climb ends at the first index of the current maximum.
Function
findFirstClimb(elevation: int[]) → int[]Examples
Example 1
elevation = [3,2,1,0,0,1,2,2,3,5,10,10,7,15]return = [4,10]The last zero before the rise is index 4. The first elevation 10 is at index 10, and the later loss of 3 exceeds 20% of the gain of 10, so the climb ends there.
Example 2
elevation = [0,5,4,6]return = [0,3]The one-unit dip is exactly 20% of the gain to 5 and is followed by a new maximum of 6, so the climb continues.
Example 3
elevation = [5,4,4,1]return = []The samples never rise, so there is no climb.
Constraints
2 <= elevation.length <= 100000-1000000 <= elevation[i] <= 1000000- All threshold comparisons must use the exact integer rule
5 * loss <= gain.