Trail valley count
EasyOnline Assessment
Count the valleys on a hiking trail from a list of altitudes recorded at checkpoints.
heights holds the altitude at each checkpoint, in walking order. Neighbouring checkpoints can have the same altitude, so the trail has flat stretches. First treat each flat stretch (a maximal run of consecutive equal altitudes) as a single stretch with that one altitude.
A stretch is a valley when all of these hold:
- There is a stretch immediately before it and one immediately after it (the first and last stretch of the trail are never valleys).
- Both neighbouring stretches are strictly higher than it.
- Its depth is at least
min_depth, where depth is how far the valley's altitude lies below the lower of its two neighbouring stretches.
Return how many valleys the trail has. An empty trail has none.
Input: heights, the altitudes in order; min_depth, the smallest depth that counts.
Output: the number of valleys, as an integer.
Example 1
- Input:
- [[5,3,6,6,2,2,7],2]
- Output:
- 2
- Explanation
- Collapsing flat stretches leaves the levels 5, 3, 6, 2, 7. The 3 lies between 5 and 6, so its depth is min(5, 6) - 3 = 2, which meets the minimum of 2. The 6 is a peak. The flat 2-2 stretch counts once: its depth is min(6, 7) - 2 = 4. Two valleys.
Example 2
- Input:
- [[1,9,4,4,8,1],5]
- Output:
- 0
- Explanation
- The 1 at the start has nothing before it and the 1 at the end has nothing after it, so neither counts. The flat 4-4 stretch is lower than 9 and 8, but its depth is min(9, 8) - 4 = 4, which is below the required 5. Result 0.
Example 3
- Input:
- [[8,3,8,4,8,5,9],4]
- Output:
- 2
- Explanation
- Levels are 8, 3, 8, 4, 8, 5, 9. The dips are 3 (depth 5), 4 (depth 4) and 5 (depth min(8, 9) - 5 = 3). With min_depth 4, the first two count. Result 2.
Constraints
0 <= heights.length <= 1,0000 <= heights[i] <= 10,0001 <= min_depth <= 10,000