984. Odd-Even Leaps
A rabbit hops along a row of platforms whose heights are given in arr. From platform i it makes leaps numbered 1, 2, 3, ... to platforms further right. On an odd-numbered leap it goes to the platform j > i with the smallest height that is at least arr[i]; on an even-numbered leap it goes to the platform j > i with the largest height that is at most arr[i]. When several platforms have that height, the leftmost is taken. If no such platform exists, the rabbit is stuck.
A starting index is good if the rabbit, beginning with leap number 1, can eventually stand on the last index. Return the number of good starting indices.
Example 1
- Input:
- arr = [4,7,2,7,3,5]
- Output:
- 4
- Explanation:
Starts 0, 1, 4 and 5 can all reach the last index (for example 1 → 3 → 5 by an odd then an even leap), while starts 2 and 3 get stuck, so the count is 4.
Example 2
- Input:
- arr = [2,2,2,9,1]
- Output:
- 4
- Explanation:
Starting at 0 the leaps go 0 → 1 → 2 → 3 → 4, and starts 1, 2 and 4 also finish; start 3 (value 9) has no odd leap, so the answer is 4.
Constraints
- 1 ≤ arr.length ≤ 105
- 0 ≤ arr[i] < 105
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 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)