2770. Maximum Number of Jumps to Reach the Last Index

Array
Dynamic Programming

TIME

O(n²)

SPACE

O(n)

Intuition

Jumps only go from a smaller index to a larger index, so the graph is acyclic. That makes dynamic programming natural.

Let dp[i] be the maximum number of jumps needed to reach index i from index 0. If index i is unreachable, keep dp[i] = -1.

For every reachable index i, try jumping to every later index j. If the value difference is within target, update dp[j].

Approach

Initialize dp[0] = 0.
Set every other dp[i] to -1.
For each index i:
- skip it if dp[i] == -1
- check every j > i
- if abs(nums[j] - nums[i]) <= target, update dp[j] = max(dp[j], dp[i] + 1)
Return dp[n - 1].

Complexity

Time: O(n²), every pair (i, j) with i < j may be checked
Space: O(n), for the DP array

Edge Cases

target = 0 -> only equal-valued jumps are valid
Last index unreachable -> return -1
Negative values -> absolute difference comparison still applies
Direct jump from 0 to n - 1 -> valid but may not be maximum

Code

from typing import List


class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        """
        2770. Maximum Number of Jumps to Reach the Last Index
        Time: O(n²)
        Space: O(n)
        """
        n = len(nums)
        dp = [-1] * n
        dp[0] = 0

        for i in range(n):
            if dp[i] == -1:
                continue

            for j in range(i + 1, n):
                if abs(nums[j] - nums[i]) <= target:
                    dp[j] = max(dp[j], dp[i] + 1)

        return dp[-1]

/**
 * 2770. Maximum Number of Jumps to Reach the Last Index
 * Time: O(n²)
 * Space: O(n)
 */
class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];

        for (int i = 1; i < n; i++) {
            dp[i] = -1;
        }

        for (int i = 0; i < n; i++) {
            if (dp[i] == -1) {
                continue;
            }

            for (int j = i + 1; j < n; j++) {
                long diff = (long) nums[j] - nums[i];
                if (Math.abs(diff) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}