Minimum number of jumps to reach the end of the array

Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. (Full Question)

• The number of jumps needed to reach the end of an array depends on each of the array values
• one, when the length given array(nums) is less than or equal to 1 there, would not be a need for any jump you are already at the destination/goal(number of jumps=0)
• when the first element of the array is 0 then there is no way to proceed ahead making all other goals impossible to reach(number of jumps should indicate something invalid -1 or Integer.MAX_VALUE)
• first, we will take a recursive approach with a low and a high; low being the start from where the jump would be initiated and high would be the ultimate destination or the goal
• each time we take a low/ start from 0 to the end of the array and check how many jumps need to be taken based on the values at the low(nums[low])

/*Helper method for recursive calls*/
public int minjump(int[] nums, int low, int high){
int jumps=0;
int min=Integer.MAX_VALUE;
if(low==high)
return 0;
if(nums[low]==0)
return Integer.MAX_VALUE;
for(int i=low+1; i<=high && i<=low+nums[low]; i++){
jumps=minjump(nums,i,high);
if(jumps!=Integer.MAX_VALUE && jumps+1<min)
min=jumps+1;
}
return min;
}

public int jump(int[] nums) {
int low=0;
int high=nums.length-1;
return minjump(nums,low,high);
}

• Now this solution takes O(n²) time complexity since for each i value we find the value of the jump by iterating the entire array and O(1) space complexity ignoring the recursive stack space
• since we calculate the value of the jump for each recursive call this particular solution can be optimized by just saving the jump values in an array
• we take an array with length same as nums, initially, we would keep all values initialized to Integer.MAX_VALUE
• Then we iterate for every index from 0 to i to decide on the jump value and update the array respectively

public int jump(int[] nums) {
int[] jumps= new int[nums.length];
int i,j;
jumps[0]=0;
if(nums.length==0 && nums[0]==0)
return Integer.MAX_VALUE;
for(i=1;i<nums.length;i++){
jumps[i]=Integer.MAX_VALUE;
for(j=0;j<i;j++){
if(i<=j+nums[j] && jumps[j]!=Integer.MAX_VALUE)
{
jumps[i]=Math.min(jumps[i],jumps[j]+1);
break;
}
}
}
return jumps[nums.length-1];
}

• This take O(n²) time complexity and O(n) extra space
• There is a better way to optimize this, the process in both the algorithms above is to check the jumps to reach some maximum limit
• Let us keep hold of a max reach variable that indicates the maximum limit one could reach from a point of start(this would be nums[i] for any i from 0 to the array length), initially value of nums[0] considering our start point
• We will also keep a variable called steps that would indicate how many steps can be taken from a particular index, initially nums[0]
• a jump variable which would keep track of the jump which we would initially set to 1 considering we take a jump to get started and move
• max Reach is updated for each index to a minimum value among the existing max Reach and the index+ nums[index]
• each time we proceed with the index we take one extra step; decrementing the step value
• as we take a step if the steps end up reducing the value to zero then that means we are out of steps and hence one has to jump; increment the jump variable
• now if the index is greater or equal to the max reach this means the index is not reachable and hence one should terminate and return Integer.MAX_VALUE indicating the impossible scenario
• when we reach the destination; that is our cue to return the jump value

public int jump(int[] nums) {
    if(nums.length<=1)
        return 0;
    if(nums[0]==0)
        return -1;
    int maxReach=nums[0];
    int steps=nums[0]; 
    int jumps=1;
    for(int i=1;i<nums.length;i++){
        if(i==nums.length-1)
            return jumps;
        maxReach=Math.max(maxReach, i+nums[i]);
        steps--;
        if(steps==0){
            jumps++;
            if(i>=maxReach)
                return -1;
            steps=maxReach-i;
        }
    }
    return -1;
}

• This algorithm is quite efficient; it has a time complexity of O(n) with O(1) space complexity