In the Leetcode Jump Game II problem solution You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n – 1]. The test cases are generated such that you can reach nums[n – 1].
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 1000
- It’s guaranteed that you can reach nums[n – 1].
Solution in C Programming
int jump(int* nums, int numsSize) {
int now = 0,ret = 0,last = 0;
for(int i = 0; now < numsSize -1; i++){
if(nums[i] + i > now)
now = nums[i] + i;
if(i == last)
++ret,last = now;
}
return (now > last)? ret + 1 : ret;
}Solution in C++ Programming
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size() ;
for(int i=1;i<n;i++){
nums[i]=max(nums[i]+i , nums[i-1]);
}
int ans=0;
int idx=0; //idx=index
while(idx<n-1){
ans++;
idx=nums[idx];
}
return ans;
}
};Solution in Java Programming
class Solution {
public int jump(int[] nums) {
return minJumps(nums);
}
public int jumpRecur(int[] nums) {
int[] minJumps = new int[1];
minJumps[0] = Integer.MAX_VALUE;
jumpRecurHelper(nums, 0, 0, minJumps);
return minJumps[0];
}
public void jumpRecurHelper(int[] nums, int index, int jumps, int[] minJumps) {
if(index >= nums.length) {
minJumps[0] = Math.min(minJumps[0], jumps);
return;
}
for(int i = 1; i <= nums[index]; i++) {
jumpRecurHelper(nums, index + i, jumps + 1, minJumps);
}
}
public int jumpMemo(int[] nums) {
return -1;
}
public int jumpMemoHelper(int[] nums) {
return -1;
}
public int minJumps(int[] nums) {
int currentJumpEnd = 0;
int farthestNextJump = 0;
int jumps = 0;
// we use -1 here because we need to see how many jumps
// to get to the last index
for(int i = 0; i < nums.length-1; i++) {
// has the effect of selecting the max jump
// from the set of jumps available between
// the start of the current jump and currentJumpEnd
farthestNextJump = Math.max(farthestNextJump, nums[i] + i);
if(i == currentJumpEnd) {
currentJumpEnd = farthestNextJump;
farthestNextJump = -1;
++jumps;
}
}
return jumps;
}
public int jumpDp(int[] nums) {
// minJumps[i] = min # of jumps to get to the ith index from the start index
int[] minJumps = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
}
return -1;
}
}Solution in Python Programming
class Solution:
def jump(self, nums):
l=r=0
cnt=0
idx=0
while r<len(nums)-1:
farthest=0
for i in range(l,r+1):
farthest=max(farthest,i+nums[i])
l=r+1
r=farthest
cnt+=1
idx+=1
return cntSolution in C# Programming
public class Solution {
public int Jump(int[] nums) {
int len = nums.Length;
if (len <= 1) {return 0;}
int level = 0;
int currEnd = 0;
int furthest = 0;
for (int i = 0; i < len; i++)
{
furthest = Math.Max(furthest, nums[i] + i);
if (furthest >= len - 1) {return level + 1;}
if (i == currEnd)
{
currEnd = furthest;
level++;
}
}
return -1; // Cannot reach the last element
}
}Also read,