#1340
Jump Game V
expert · 1085 · lc hard +32 · verified · 64.8% accepted · 1,188 likes · top 68%
Description
Given an integer array arr and integer d, you can jump from index i up to d positions left or right to reach index j, provided arr[i] strictly exceeds arr[j] and also strictly exceeds every element between i and j. Start at any index. Return the maximum number of distinct indices visitable in any sequence of valid jumps.
You may never jump outside the array.
Example 1:
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.
Example 2:
Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.
Example 3:
Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.
Code
1
2
3