heights and an integer span. Index i is a valley point if:
- span ≤ i < len(heights) − span;
- the span values right before i are non-increasing (each one is no greater than the one before it);
- the span values right after i are non-decreasing (each one is no smaller than the one before it).
The value heights[i] itself plays no part in the check.
Return all valley points in increasing order.heights=[5, 4, 4, 2, 3, 6, 6, 1], span=2 → [2, 3, 4]
Index 2: [5, 4] on the left never rises, [2, 3] on the right never drops. Index 3: [4, 4] and [3, 6]. Index 4: [4, 2] and [6, 6]. Index 5 fails because [2, 3] on its left rises.
heights=[1, 2, 3], span=1 → [1]
The only candidate is index 1; both one-element blocks [1] and [3] trivially qualify.
heights=[3, 4, 2, 5], span=2 → []
With span = 2 an index must be at least 2 and below 2, so there are no candidates.
len(heights) ≤ 10⁵heights[i] ≤ 10⁶span ≤ len(heights) / 2heights=[5, 4, 4, 2, 3, 6, 6, 1], span=2
[2, 3, 4]
Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.