Maximum Number of Jumps to Reach the Last Index

MEDIUM

Description

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
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Approaches

Checkout 3 different approaches to solve Maximum Number of Jumps to Reach the Last Index. Click on different approaches to view the approach and algorithm in detail.

Top-Down Dynamic Programming with Memoization

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).

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 Analysis

Time Complexity: 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 Complexity: O(n). We use an O(n) `memo` array and the recursion stack can go up to O(n) deep.

Pros and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Maximum Number of Jumps to Reach the Last Index. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Number of Jumps to Reach the Last Index

Patterns:

Dynamic Programming

Data Structures:

Array