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: We use a combination of dynamic programming and depth-first search (DFS) to solve this problem effectively.
We maintain a DP array where dp[i] represents the maximum number of indices we can visit starting from index i. To fill this DP array, we perform DFS considering all possible valid jumps.
The DFS function checks all positions index – x (to the left) and index + x (to the right) from each position i where the jump is valid, i.e., the height requirement is satisfied. The result for each index is stored in the DP array to avoid recomputation and speed up the process.
The solution uses a recursive DFS approach where each index is traversed, and we check all indices reachable within distance d, both to the left and right. Using a DP array, we store results for these indices to avoid redundant computation.
Time Complexity: O(n * d), where n is the length of the array, and d is the distance constraint. Each index is visited at most once due to memoization.
Space Complexity: O(n), for the DP array used in the solution.
Approach: In this approach, we preprocess the indices based on the heights in the array, then apply dynamic programming to determine the maximum number of indices we can visit.
First, we create a sorted list of indices based on their corresponding values in the input array. We then use a DP array where dp[i] indicates the maximum number of indices we can reach starting from index i.
By iterating over this sorted list, we try to update our DP array based on valid jumps that comply with the problem's constraints. This ensures that each index is processed in order of increasing heights, allowing efficient computation of possible jumps.
This solution involves sorting the indices based on height in ascending order and uses a DP array to track the maximum indices reachable from each. Jumps are considered both left and right within distance and height constraints.
Time Complexity: O(n log n + n * d), due to sorting and checking possible positions for each index.
Space Complexity: O(n), necessitated by the storage for indices and the DP array.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Depth-First Search (DFS) | Time Complexity: O(n * d), where n is the length of the array, and d is the distance constraint. Each index is visited at most once due to memoization. Space Complexity: O(n), for the DP array used in the solution. |
| Sorting with Dynamic Programming | Time Complexity: O(n log n + n * d), due to sorting and checking possible positions for each index. Space Complexity: O(n), necessitated by the storage for indices and the DP array. |
| Default Approach | — |
| 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. |
Leetcode 1340. Jump Game V • Fraz • 4,164 views views
Watch 6 more video solutions →Practice Jump Game V with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor