309. Turning Points
A hiker's altitude readings are stored in a chain, one node per checkpoint. A checkpoint is a turning point if it is neither the first nor the last node and its altitude is strictly higher than both neighbours (a peak) or strictly lower than both neighbours (a valley). Equal altitudes never form a turning point.
Given the head of the chain, number the nodes from 0 and look at the positions of all turning points. Return [minDistance, maxDistance], where minDistance is the smallest difference between positions of any two different turning points and maxDistance is the largest. If the chain has fewer than two turning points, return [-1, -1]. The chain can hold up to 100,000 nodes.
Example 1
- Input:
- head = [2,7,3,3,9,4,6,1,5]
- Output:
- [1,6]
- Explanation:
Turning points sit at positions 1 (peak 7), 4 (peak 9), 5 (valley 4), 6 (peak 6) and 7 (valley 1); the two 3s are equal so neither qualifies. The closest pair is 1 apart and the extreme pair is positions 1 and 7, 6 apart: [1, 6].
Example 2
- Input:
- head = [5,9,9,2,3]
- Output:
- [-1,-1]
- Explanation:
The 9s are equal, so neither is a peak. Only the 2 (a valley) is a turning point, which is fewer than two: [-1, -1].
Constraints
0 ≤ chain length ≤ 105
-109 ≤ node value ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)