Skip to content

2770. Maximum Number of Jumps to Reach the Last Index

SourceWeekly Contest 353 Q2DifficultyMediumRating1533

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

Solutions

Solution 1: Memoization

Thinking

Jump from index \(0\) to the end, each step requiring an absolute difference at most \(\textit{target}\), and maximize the number of jumps. \(n\le 1000\); a shortest-path formulation would minimize jumps instead.

\(\textit{dfs}(i)\) is the most jumps from \(i\): take \(1+\textit{dfs}(j)\) over legal \(j>i\), \(0\) at the end, and \(-\infty\) when no jump exists. If the memoized value is negative, return \(-1\).

For each position \(i\), we consider to jump to position \(j\) which satisfies \(|\textit{nums}[i] - \textit{nums}[j]| \leq \textit{target}\). Then we can jump from \(i\) to \(j\), and continue to jump from \(j\) to the end.

Therefore, we design a function \(\textit{dfs}(i)\), which represents the maximum number of jumps needed to jump to the end index starting from position \(i\). Then the answer is \(\textit{dfs}(0)\).

The calculation process of function \(\textit{dfs}(i)\) is as follows:

  • If \(i = n - 1\), then we have reached the end index and no jumps are required, so return \(0\);
  • Otherwise, we need to enumerate the positions \(j\) that can be jumped from position \(i\), and calculate the maximum number of jumps needed to jump to the end index starting from \(j\), then \(\textit{dfs}(i)\) is equal to the maximum value of all \(\textit{dfs}(j)\) plus \(1\). If there is no position \(j\) that can be jumped from \(i\), then \(\textit{dfs}(i) = -\infty\).

To avoid duplicate calculations, we can use memoization.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == n - 1:
                return 0
            ans = -inf
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) <= target:
                    ans = max(ans, 1 + dfs(j))
            return ans

        n = len(nums)
        ans = dfs(0)
        return -1 if ans < 0 else ans

 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
28
29
30
31
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;
    }
}

 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
class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        int f[n];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i == n - 1) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            f[i] = -(1 << 30);
            for (int j = i + 1; j < n; ++j) {
                if (abs(nums[i] - nums[j]) <= target) {
                    f[i] = max(f[i], 1 + dfs(j));
                }
            }
            return f[i];
        };
        int ans = dfs(0);
        return ans < 0 ? -1 : ans;
    }
};

 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
28
29
30
31
32
33
34
35
func maximumJumps(nums []int, target int) int {
    n := len(nums)
    f := make([]int, n)
    for i := range f {
        f[i] = -1
    }
    var dfs func(int) int
    dfs = func(i int) int {
        if i == n-1 {
            return 0
        }
        if f[i] != -1 {
            return f[i]
        }
        f[i] = -(1 << 30)
        for j := i + 1; j < n; j++ {
            if abs(nums[i]-nums[j]) <= target {
                f[i] = max(f[i], 1+dfs(j))
            }
        }
        return f[i]
    }
    ans := dfs(0)
    if ans < 0 {
        return -1
    }
    return ans
}

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
18
19
20
21
function maximumJumps(nums: number[], target: number): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(-1);
    const dfs = (i: number): number => {
        if (i === n - 1) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        f[i] = -(1 << 30);
        for (let j = i + 1; j < n; ++j) {
            if (Math.abs(nums[i] - nums[j]) <= target) {
                f[i] = Math.max(f[i], 1 + dfs(j));
            }
        }
        return f[i];
    };
    const ans = dfs(0);
    return ans < 0 ? -1 : ans;
}

 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
impl Solution {
    pub fn maximum_jumps(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut f = vec![-1; n];

        fn dfs(i: usize, nums: &Vec<i32>, target: i32, f: &mut Vec<i32>) -> i32 {
            if i == nums.len() - 1 {
                return 0;
            }
            if f[i] != -1 {
                return f[i];
            }
            f[i] = -(1 << 30);
            for j in i + 1..nums.len() {
                if (nums[i] - nums[j]).abs() <= target {
                    f[i] = f[i].max(1 + dfs(j, nums, target, f));
                }
            }
            f[i]
        }

        let ans = dfs(0, &nums, target, &mut f);
        if ans < 0 { -1 } else { ans }
    }
}

Solution 2: Dynamic Programming

Thinking

Enumerating every jump sequence is exponential. The array length reaches \(1000\), and a legal step to the next index is always tried first, so the search has depth \(n\). The most jumps from index \(i\) depend only on later indexes. Let \(f[i]\) be that number, with \(f[n-1]=0\), and scan landing indexes from the right, updating with \(1+f[j]\) when the absolute difference is at most \(\textit{target}\). A still-negative \(f[0]\) means the end is unreachable, so the answer is \(-1\).

Let \(f[i]\) be the maximum number of jumps from index \(i\) to the end. Set \(f[n-1]=0\) and every earlier entry to \(-\infty\). For \(i\) from \(n-2\) down to \(0\), enumerate a landing index \(j\) (\(i < j < n\)). If \(|\textit{nums}[i]-\textit{nums}[j]| \leq \textit{target}\), update \(f[i]\) with \(1+f[j]\). If \(f[0]\) is still negative, the end cannot be reached and the answer is \(-1\); otherwise the answer is \(f[0]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [-inf] * n
        f[-1] = 0
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) <= target:
                    f[i] = max(f[i], 1 + f[j])
        return -1 if f[0] < 0 else f[0]

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(n, -(1 << 30));
        f[n - 1] = 0;
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (abs(nums[i] - nums[j]) <= target) {
                    f[i] = max(f[i], 1 + f[j]);
                }
            }
        }
        return f[0] < 0 ? -1 : f[0];
    }
};

 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
func maximumJumps(nums []int, target int) int {
    n := len(nums)
    f := make([]int, n)
    for i := range f {
        f[i] = -(1 << 30)
    }
    f[n-1] = 0
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if abs(nums[i]-nums[j]) <= target {
                f[i] = max(f[i], 1+f[j])
            }
        }
    }
    if f[0] < 0 {
        return -1
    }
    return f[0]
}

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
function maximumJumps(nums: number[], target: number): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(-(1 << 30));
    f[n - 1] = 0;
    for (let i = n - 2; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            if (Math.abs(nums[i] - nums[j]) <= target) {
                f[i] = Math.max(f[i], 1 + f[j]);
            }
        }
    }
    return f[0] < 0 ? -1 : f[0];
}

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

Comments