Problem

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 themaximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8
9

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

1
2
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] <= 10^9
  • 0 <= target <= 2 * 109

Solution

Method 1 – Dynamic Programming

Intuition

We want to maximize the number of jumps to reach the last index, where each jump from i to j is allowed if the difference between nums[j] and nums[i] is within [-target, target]. We can use dynamic programming to track the maximum jumps to each index.

Approach

  1. Initialize a dp array of size n with all values as -1, except dp[0] = 0 (start position).
  2. For each index i from 0 to n-1:
    • For each j from i+1 to n-1:
      • If abs(nums[j] - nums[i]) <= target:
        • If dp[i] != -1, update dp[j] = max(dp[j], dp[i] + 1).
  3. The answer is dp[n-1].
  4. If dp[n-1] is still -1, return -1 (not reachable).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(n, -1);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] == -1) continue;
            for (int j = i + 1; j < n; ++j) {
                if (abs(nums[j] - nums[i]) <= target) {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n-1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func maximumJumps(nums []int, target int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = -1
    }
    dp[0] = 0
    for i := 0; i < n; i++ {
        if dp[i] == -1 {
            continue
        }
        for j := i + 1; j < n; j++ {
            if abs(nums[j]-nums[i]) <= target {
                if dp[j] < dp[i]+1 {
                    dp[j] = dp[i] + 1
                }
            }
        }
    }
    return dp[n-1]
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == -1) continue;
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n-1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maximumJumps(nums: IntArray, target: Int): Int {
        val n = nums.size
        val dp = IntArray(n) { -1 }
        dp[0] = 0
        for (i in 0 until n) {
            if (dp[i] == -1) continue
            for (j in i+1 until n) {
                if (kotlin.math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = maxOf(dp[j], dp[i] + 1)
                }
            }
        }
        return dp[n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maximumJumps(self, nums: list[int], target: int) -> int:
        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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn maximum_jumps(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut dp = vec![-1; n];
        dp[0] = 0;
        for i in 0..n {
            if dp[i] == -1 { continue; }
            for j in i+1..n {
                if (nums[j] - nums[i]).abs() <= target {
                    dp[j] = dp[j].max(dp[i] + 1);
                }
            }
        }
        dp[n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maximumJumps(nums: number[], target: number): number {
        const n = nums.length;
        const dp = Array(n).fill(-1);
        dp[0] = 0;
        for (let i = 0; i < n; i++) {
            if (dp[i] === -1) continue;
            for (let j = i + 1; j < n; j++) {
                if (Math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n-1];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since for each index we may check all following indices.
  • 🧺 Space complexity: O(n), for the dp array.