LeetCode 2770. Maximum Number of Jumps to Reach the Last Index Solution in Java, C++, Python & More | Explanation + Code

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

For each position i, we consider to jump to position j which satisfies |nums[i] - nums[j]| ≤ 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) = -∞.

To avoid duplicate calculations, we can use memoization.

Time complexity O(n²), space complexity O(n). where n is the length of array.

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)