Problem Statement in English

You’re given an array of integers nums and an integer target. You can jump from index i to index j if the following conditions are satisfied:

  • i < j < nums.length
  • abs(nums[i] - nums[j]) <= target

Return the maximum number of jumps you can make to reach the last index of the array. If it’s not possible to reach the last index, return -1.

Approach

There are overlapping subproblems here. The solution to an index depends on the solution to the indices that come after it. This is a classic case for dynamic programming.

We can use a bottom-up approach to fill a dp array where dp[i] represents the maximum number of jumps to reach the end from index i. We start from the end and move backwards, checking all possible jumps from each index, using the solution that we have already computed for the indices that come after it.

And we’re done!

Solution in Python


class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [-inf] * n
        dp[-1] = 0

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

        return max(-1, dp[0])

Complexity

  • Time: $O(n^2)$
    Since we have a nested loop.

  • Space: $O(n)$
    Since we use a dp array of size n.

And we are done.