Scale Engineer

Maximum Number of Jumps to Reach the Last Index

Med
#2487Time: 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.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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] <= 109
  • 0 <= 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 memo array of size n and initialize it with a sentinel value.
  • Define a recursive function solve(currentIndex).
  • Base Case: If currentIndex is 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).

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem