2770. Maximum Number of Jumps to Reach the Last Index LeetCode Solution
In this guide, you will get 2770. Maximum Number of Jumps to Reach the Last Index LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Jumps to Reach the Last Index problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Jumps to Reach the Last Index
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.
2770. Maximum Number of Jumps to Reach the Last Index LeetCode Solution in C++
class Solution {
public:
int maximumJumps(vector<int>& nums, int target) {
const int n = nums.size();
// dp[i] := the maximum number of jumps to reach i from 0
vector<int> dp(n, -1);
dp[0] = 0;
for (int j = 1; j < n; ++j)
for (int i = 0; i < j; ++i)
if (dp[i] != -1 && abs(nums[j] - nums[i]) <= target)
dp[j] = max(dp[j], dp[i] + 1);
return dp[n - 1];
}
}; /* code provided by PROGIEZ */
2770. Maximum Number of Jumps to Reach the Last Index LeetCode Solution in Java
class Solution {
public int maximumJumps(int[] nums, int target) {
final int n = nums.length;
// dp[i] := the maximum number of jumps to reach i from 0
int[] dp = new int[n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int j = 1; j < n; ++j)
for (int i = 0; i < j; ++i)
if (dp[i] != -1 && Math.abs(nums[j] - nums[i]) <= target)
dp[j] = Math.max(dp[j], dp[i] + 1);
return dp[n - 1];
}
} // code provided by PROGIEZ
2770. Maximum Number of Jumps to Reach the Last Index LeetCode Solution in Python
class Solution:
def maximumJumps(self, nums: list[int], target: int) -> int:
n = len(nums)
# dp[i] := the maximum number of jumps to reach i from 0
dp = [-1] * n
dp[0] = 0
for j in range(1, n):
for i in range(j):
if dp[i] != -1 and abs(nums[j] - nums[i]) <= target:
dp[j] = max(dp[j], dp[i] + 1)
return dp[-1] # code by PROGIEZ
