Watch 7 video solutions for Jump Game V, a hard level problem involving Array, Dynamic Programming, Sorting. This walkthrough by Fraz has 4,164 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of integers arr and an integer d. In one step you can jump from index i to index:
i + x where: i + x < arr.length and 0 < x <= d.i - x where: i - x >= 0 and 0 < 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.lengthProblem Overview: You are given an array arr where each value represents height. From index i, you can jump left or right up to d positions, but only to a strictly smaller value and you cannot jump over a taller or equal element. The task is to compute the maximum number of indices you can visit starting from any index.
Approach 1: Dynamic Programming with Depth‑First Search (DFS) (Time: O(n*d), Space: O(n))
This approach treats the array like a directed graph where edges represent valid jumps. For each index i, run a DFS that explores up to d steps left and right until hitting a boundary or a value greater than or equal to arr[i]. Use memoization so each index stores the maximum jumps possible starting there. During DFS, compute 1 + dfs(nextIndex) and keep the maximum. The memo table avoids recomputation, turning what would be exponential exploration into linear dynamic programming. This approach is intuitive and directly models the constraints of the problem.
Approach 2: Sorting with Dynamic Programming (Time: O(n log n + n*d), Space: O(n))
Instead of exploring recursively, process indices in increasing order of their heights. Sorting ensures that when you process an index, all potential jump destinations (which must have smaller heights) are already computed. For each index, scan left and right up to distance d while values remain smaller. Update dp[i] = max(dp[i], 1 + dp[j]) for every valid jump target j. Sorting eliminates recursion and guarantees that dependencies are resolved beforehand, making the dynamic programming transition straightforward.
Recommended for interviews: The memoized DFS approach is typically expected. It clearly shows the problem as graph traversal combined with dynamic programming. Mentioning the sorted DP optimization demonstrates deeper understanding and familiarity with alternative strategies involving arrays and sorting. Start with DFS + memoization for clarity, then discuss the ordered DP idea if asked about optimizations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with DFS (Memoization) | O(n*d) | O(n) | General solution. Best for interviews because it models the problem as graph traversal with memoized DP. |
| Sorting with Dynamic Programming | O(n log n + n*d) | O(n) | When you want to avoid recursion and process states in dependency order using sorted heights. |