Jump Game V
HardPrompt
Given an array of integers arr and an integer d. In one step you can jump from index i to index:
i + xwhere:i + x < arr.lengthand0 < x <= d.i - xwhere:i - x >= 0and0 < x <= d.
In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).
You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.
Notice that you can not jump outside of the array at any time.
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.
Constraints:
1 <= arr.length <= 10001 <= arr[i] <= 1051 <= d <= arr.length
Approaches
2 approaches with complexity analysis and trade-offs.
This approach significantly improves upon the brute-force method by using memoization, a key technique in dynamic programming. We observe that the recursive function dfs(i) is called multiple times with the same index i, leading to redundant computations. By storing the result of dfs(i) the first time it's computed and reusing it for subsequent calls, we can reduce the time complexity from exponential to polynomial. This is also known as top-down dynamic programming.
Algorithm
- Create a memoization array
memoof sizen, initialized to 0.memo[i]will store the result of the longest path starting fromi. - Define a recursive function
dfs(i). - Inside
dfs(i), first check ifmemo[i]is non-zero. If so, a result has been computed, so returnmemo[i]. - Initialize
res = 1. - Explore jumps to the right (from
i+1tomin(i+d, n-1)). Stop if a blocking element (arr[j] >= arr[i]) is found. For each valid jump toj, updateres = max(res, 1 + dfs(j)). - Explore jumps to the left (from
i-1tomax(0, i-d)) similarly. - Store the final result in
memo[i] = resand return it. - The main function calls
dfs(i)for allifrom0ton-1and returns the maximum value obtained.
Walkthrough
We augment the recursive solution with a memoization table, typically an array memo, to store the results of subproblems. memo[i] will hold the maximum number of indices that can be visited starting from index i.
The algorithm is as follows:
- Initialize a
memoarray of the same size asarrwith a sentinel value (e.g., 0) to indicate that the result for that index has not been computed yet. - Modify the
dfs(i)function. At the beginning of the function, check ifmemo[i]already contains a computed result. If it does, return that value immediately. - If
memo[i]has not been computed, proceed with the same logic as the brute-force approach: calculate the maximum path length by exploring valid jumps to the left and right and making recursive calls. - Once the result for
iis computed, store it inmemo[i]before returning. - The main loop still iterates through all indices
ias starting points, calling the memoizeddfs(i)and tracking the overall maximum.
This ensures that the longest path for each index is calculated exactly once.
class Solution { int[] memo; int[] arr; int d; int n; public int maxJumps(int[] arr, int d) { this.n = arr.length; this.arr = arr; this.d = d; this.memo = new int[n]; int maxJumps = 0; for (int i = 0; i < n; i++) { maxJumps = Math.max(maxJumps, dfs(i)); } return maxJumps; } private int dfs(int i) { if (memo[i] != 0) { return memo[i]; } int res = 1; // Jump to the right for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) { if (arr[j] >= arr[i]) { break; } res = Math.max(res, 1 + dfs(j)); } // Jump to the left for (int j = i - 1; j >= Math.max(0, i - d); j--) { if (arr[j] >= arr[i]) { break; } res = Math.max(res, 1 + dfs(j)); } memo[i] = res; return res; }}Complexity
Time
O(n * d). Each state `dfs(i)` for `i` from 0 to `n-1` is computed exactly once. The work done within each call is proportional to `d` because of the two loops exploring up to `d` indices in each direction.
Space
O(n), where n is the array length. This space is used for the memoization array `memo` and the recursion stack.
Trade-offs
Pros
Highly efficient and sufficient to pass the given constraints.
Often intuitive to derive from a brute-force recursive solution.
Asymptotically faster than a sorting-based bottom-up approach for this problem.
Cons
Relies on recursion, which can have overhead and stack depth limitations in some environments (though not an issue for n=1000).
Slightly more complex than the brute-force approach due to the memoization table.
Solutions
Solution
class Solution {private int n;private int d;private int[] arr;private Integer[] f;public int maxJumps(int[] arr, int d) { n = arr.length; this.d = d; this.arr = arr; f = new Integer[n]; int ans = 1; for (int i = 0; i < n; ++i) { ans = Math.max(ans, dfs(i)); } return ans; }private int dfs(int i) { if (f[i] != null) { return f[i]; } int ans = 1; for (int j = i - 1; j >= 0; --j) { if (i - j > d || arr[j] >= arr[i]) { break; } ans = Math.max(ans, 1 + dfs(j)); } for (int j = i + 1; j < n; ++j) { if (j - i > d || arr[j] >= arr[i]) { break; } ans = Math.max(ans, 1 + dfs(j)); } return f[i] = ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.