Welcome to Subscribe On Youtube
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
-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] | \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.
-
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; } };
-
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
-
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 } func max(a, b int) int { if a > b { return a } return b }
-
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; }