2770. Maximum Number of Jumps to Reach the Last Index

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⁹

Solutions

Solution 1: Memoization

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

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

The calculation process of function \(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 \(dfs(i)\) is equal to the maximum value of all \(dfs(j)\) plus \(1\). If there is no position \(j\) that can be jumped from \(i\), then \(dfs(i) = -\infty\).

To avoid duplicate calculations, we can use memoization.

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

Python3JavaC++GoTypeScript

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

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;
    }
}

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        int f[n];
        memset(f, -1, sizeof(f));
        function<int(int)> dfs = [&](int i) {
            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;
    }
};

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
}

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;
}

2770. Maximum Number of Jumps to Reach the Last Index

Description

Solutions

Solution 1: Memoization

Comments