Maximum Number of Jumps to Reach the Last Index
MedPrompt
You are given a 0-indexed array nums of n integers and an integer target.
You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:
0 <= i < j < n-target <= nums[j] - nums[i] <= target
Return the maximum number of jumps you can make to reach index n - 1.
If there is no way to reach index n - 1, return -1.
Example 1:
Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. Example 2:
Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. Example 3:
Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.
Constraints:
2 <= nums.length == n <= 1000-109 <= nums[i] <= 1090 <= target <= 2 * 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach optimizes the brute-force recursion by using memoization. We store the results of subproblems in a cache (an array) so that each subproblem is solved only once. This transforms the exponential complexity into a polynomial one.
Algorithm
- Create a
memoarray of sizenand initialize it with a sentinel value. - Define a recursive function
solve(currentIndex). - Base Case: If
currentIndexis 0, return 0. - Memoization Check: If
memo[currentIndex]is not the sentinel value, return it. - Compute the result as in the brute-force approach.
- Store the computed result in
memo[currentIndex]before returning. - The final answer is
solve(n-1).
Walkthrough
The core idea is the same as the recursive approach, but we introduce a memo array to store the results. The memo array is initialized with a sentinel value (e.g., -2) to indicate that a subproblem has not been computed yet.
When the recursive function solve(i) is called, it first checks if memo[i] already contains a computed result. If it does, the stored value is returned immediately, avoiding redundant computation.
If the result is not in the memoization table, the function computes it as in the brute-force approach, by checking all possible previous jumps.
Before returning, the computed result for solve(i) is stored in memo[i]. This ensures that any subsequent call to solve(i) will be an O(1) lookup.
This technique is also known as top-down dynamic programming.
import java.util.Arrays; class Solution { private int[] memo; public int maximumJumps(int[] nums, int target) { int n = nums.length; memo = new int[n]; // Initialize memo with -2 to distinguish from the result -1 (unreachable). Arrays.fill(memo, -2); return solve(nums, target, n - 1); } private int solve(int[] nums, int target, int currentIndex) { if (currentIndex == 0) { return 0; } if (memo[currentIndex] != -2) { return memo[currentIndex]; } int maxJumps = -1; for (int i = 0; i < currentIndex; i++) { if (Math.abs((long)nums[currentIndex] - nums[i]) <= target) { int prevJumps = solve(nums, target, i); if (prevJumps != -1) { maxJumps = Math.max(maxJumps, prevJumps + 1); } } } return memo[currentIndex] = maxJumps; }}Complexity
Time
O(n^2). Each state `dp[i]` is computed only once. To compute each state, we iterate through up to `i` previous states. The total work is the sum of `1 + 2 + ... + (n-1)`, which is O(n^2).
Space
O(n). We use an O(n) `memo` array and the recursion stack can go up to O(n) deep.
Trade-offs
Pros
Drastically more efficient than brute-force.
Guaranteed to pass within the time limits.
Maintains a recursive structure which can be intuitive.
Cons
Slightly more space usage than the bottom-up approach due to the recursion stack.
Can lead to stack overflow for very large
n(not an issue here).
This is an iterative dynamic programming approach. We build the solution from the ground up, starting from the base case (index 0) and iteratively computing the solution for all indices up to n-1. This avoids recursion and is generally the most efficient implementation for this type of DP problem.
Algorithm
- Create a
dparray of sizen. - Initialize
dp[0] = 0and all other elements to -1. - Loop
ifrom 1 ton-1. - Inside, loop
jfrom 0 toi-1. - If
dp[j]is not -1 and a jump fromjtoiis valid, updatedp[i] = max(dp[i], dp[j] + 1). - After the loops, return
dp[n-1].
Walkthrough
We use a dp array of size n, where dp[i] will store the maximum number of jumps to reach index i from the start.
We initialize dp[0] = 0 because we are at the starting index with 0 jumps. All other dp[i] are initialized to -1 to signify that they are currently unreachable.
We then iterate with an outer loop from i = 1 to n-1. For each i, we want to compute dp[i].
To do this, an inner loop iterates through all previous indices j from 0 to i-1.
Inside the inner loop, we check if index j is reachable (dp[j] != -1) and if a jump from j to i is valid (abs(nums[i] - nums[j]) <= target).
If both conditions are met, it means we can reach i from j. The number of jumps would be dp[j] + 1. We update dp[i] to be the maximum of its current value and dp[j] + 1.
After the loops complete, dp[n-1] will hold the maximum number of jumps to reach the last index, or -1 if it's unreachable.
import java.util.Arrays; class Solution { public int maximumJumps(int[] nums, int target) { int n = nums.length; int[] dp = new int[n]; // Initialize dp array with -1 to represent unreachable states. Arrays.fill(dp, -1); // Base case: 0 jumps to reach index 0. dp[0] = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // Check if index j is reachable and the jump from j to i is valid. if (dp[j] != -1 && Math.abs((long)nums[i] - nums[j]) <= target) { // If so, we can reach i from j. Update dp[i]. dp[i] = Math.max(dp[i], dp[j] + 1); } } } return dp[n - 1]; }}Complexity
Time
O(n^2). We have two nested loops. The outer loop runs `n-1` times, and the inner loop runs up to `n-1` times.
Space
O(n). We use an array of size `n` to store the DP states.
Trade-offs
Pros
Very efficient and passes the given constraints.
Avoids recursion, eliminating the risk of stack overflow and the overhead of function calls.
Often considered the canonical DP solution.
Cons
The iterative logic might be slightly less direct to formulate than the recursive top-down approach for some developers.
This approach explores all possible valid jump sequences from the starting index 0 to every other index recursively. It calculates the maximum number of jumps for each index by considering all possible previous indices from which a jump could have been made.
Algorithm
- Define a recursive function
solve(currentIndex). - Base Case: If
currentIndexis 0, return 0. - Initialize
maxJumps = -1. - Iterate through all previous indices
ifrom 0 tocurrentIndex - 1. - If a jump from
itocurrentIndexis valid andsolve(i)is not -1, updatemaxJumps = max(maxJumps, solve(i) + 1). - Return
maxJumps. - The final answer is
solve(n-1).
Walkthrough
We define a recursive function, let's call it solve(i), which calculates the maximum number of jumps to reach index i.
The base case for the recursion is solve(0), which is 0, as we start at index 0 with zero jumps.
For any other index i, we iterate through all previous indices j (from 0 to i-1). If a jump from j to i is valid (i.e., abs(nums[i] - nums[j]) <= target), we recursively call solve(j).
If solve(j) returns a valid number of jumps (not -1), it means index j is reachable. We then update the maximum jumps to reach i as max(current_max, solve(j) + 1).
If no valid jump can be made to index i, the function returns -1. The final answer is the result of solve(n-1).
This method is a straightforward translation of the problem's definition into a recursive structure. However, it's highly inefficient because it recomputes the solution for the same subproblems multiple times.
class Solution { public int maximumJumps(int[] nums, int target) { return solve(nums, target, nums.length - 1); } private int solve(int[] nums, int target, int currentIndex) { if (currentIndex == 0) { return 0; } int maxJumps = -1; for (int i = 0; i < currentIndex; i++) { // Use long for subtraction to prevent potential integer overflow. if (Math.abs((long)nums[currentIndex] - nums[i]) <= target) { int prevJumps = solve(nums, target, i); if (prevJumps != -1) { maxJumps = Math.max(maxJumps, prevJumps + 1); } } } return maxJumps; }}Complexity
Time
O(2^n). The recursive function has overlapping subproblems. The number of calls grows exponentially with `n`, leading to a Time Limit Exceeded error on larger inputs.
Space
O(n). The space is dominated by the depth of the recursion stack, which can go up to `n` in the worst case.
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Extremely inefficient due to redundant computations of the same subproblems.
Will not pass for the given constraints (n <= 1000).
Solutions
Solution
class Solution {private Integer[] f;private int[] nums;private int n;private int target;public int maximumJumps(int[] nums, int target) { n = nums.length; this.target = target; this.nums = nums; f = new Integer[n]; int ans = dfs(0); return ans < 0 ? -1 : ans; }private int dfs(int i) { if (i == n - 1) { return 0; } if (f[i] != null) { return f[i]; } int ans = -(1 << 30); for (int j = i + 1; j < n; ++j) { if (Math.abs(nums[i] - nums[j]) <= target) { ans = Math.max(ans, 1 + dfs(j)); } } return f[i] = ans; }}class Solution {public: int maximumJumps(vector<int> &nums, int target) { int n = nums.size(); int f[n]; memset(f, -1, sizeof(f)); function<int(int)> dfs = [&](int i) { if (i == n - 1) { return 0; } if (f[i] != -1) { return f[i]; } f[i] = -(1 << 30); for (int j = i + 1; j < n; ++j) { if (abs(nums[i] - nums[j]) <= target) { f[i] = max(f[i], 1 + dfs(j)); } } return f[i]; }; int ans = dfs(0); return ans < 0 ? -1 : ans; }};class Solution: def maximumJumps(self, nums: List[int], target: int) -> int: @ cache def dfs(i: int) -> int: if i == n - 1: return 0 ans = - inf for j in range(i + 1, n): if abs(nums[i] - nums[j]) <= target: ans = max(ans, 1 + dfs(j)) return ans n = len(nums) ans = dfs(0) return - 1 if ans < 0 else ansVideo 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.