Question 96 : Minimum Number of Jumps to reach last Index

 Problem

Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a jump that can be made from this index. The length of a jump can vary from 1 to A[index].4

If value on any index is zero, this means that you can not move forward from this index.

Find the minimum number of jumps required to reach the last index. If the answer is not possible for any case, print “Not Possible”.

Input :
int[] A = { 2, 3, 1, 1, 4 }
Output :
2
Input :
int[] A = { 2, 0, 0, 1, 4 }
Output :
Not Possible

Solution

APPROACH – I :
A basic brute force solution can be achieved by using a recursive approach and making calls to every possible reachable index from the current index.
Now, what does that mean?

• We are given the array where each index contains the length of the maximum jumps that can be made from that index.
  For eg if A[i] = x, this means that from index ‘i’ we can jump to index  i+0,  i+1,  i+2 … i+x  and obviously only if these indices are in bounds.
• Here making a call is equivalent to a jump for which we need to keep a jump variable in the function call and increment it in every recursive call made.
• The base case condition will be, when the current index in the function call is eventually the end index. In the base case we compare the number of jumps made to reach this end index with the global minimum variable update it if the current number of jumps made to reach end index is less than the previously global minimum jump and return from the current call. If the current index becomes greater than the last index, then return from the current call as this is not the result we are looking for.

Steps:

1. Start from index zero and initialize the number of jumps made variable to 0.
2. Now for every index that is, in every call, start a loop from 1 to value at current index in the given array indicating the lengths of jump to be made in the next call. Make the function call with current index incremented by the length of jump and number of jumps by 1.
3. When in base case, that is, when the current index in the call is equal to the last index, compare the number of jumps with the global min jumps variable, update it if the number of jumps made in this call is less than the previously global minimum jump and return from the current call.
   
4. Here we will be using reactive recursive calls, so when the current index in the call is greater than the last index, we simply return from the call without doing any comparisons
5. Time Complexity Discussion:

For an array of length n, at every index ‘i’ we are making A[i] jumps which in the worst case can be equal to n. Hence, there can be a total of ‘n’ potential calls from all the ‘n’ indices, therefore the worst time complexity of this solution is O(n^n).

package Backtracking;
 
public class minJumpsArr {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };
        /*current index and number of jumps are zero initially*/
        solve(0, A, 0);
 
        if(minJumps == (int) 1e9 + 1)
        {
            /*if the min jumps is still infinity, this means it has
             * never been updated that is, we did not reach the end
             * index even once, hence answer is not possible in this
             * case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(minJumps);
        }
 
    }
 
    /* global min variable to store the minimum number of
     * jumps required to reach last index.*/
    public static int minJumps = (int) 1e9 + 1;
 
    public static void solve(int currIdx, int[] a, int jumps) {
        /* base case : Case 1 - if current index is equal to last
         * index (destination) update the global min jumps if the
         * current number of jumps is lesser and return. 
         * Case 2 - if current index is greater than the last index,
         * simply return because this is not the result we are looking for*/
        if (currIdx >= a.length - 1) {
            if (currIdx == a.length - 1) {
                minJumps = Math.min(minJumps, jumps);
            }
            return;
        }
        /*maximum length of any jump that can be made from this index*/
        int reachableIdxs = a[currIdx];
 
        /* recursive calls for all lengths of jump varying from 1 to max
         * length and incrementing number of jumps by 1 in every call */
        for (int jumpLength = 1; jumpLength <= reachableIdxs; jumpLength++) {
            solve(currIdx + jumpLength, a, jumps + 1);
        }
    }

APPROACH 2 :

In the above recursive solution, we can clearly see a lot of redundant calls, therefore for the reduction of the number of calls and eventually for reduced time complexity, we can use Dynamic programming approach.

• For any index ‘i’ we can actually store the minimum number of jumps required to reach this index and then from here we can calculate the same for all the reachable indices from this index ‘i’ (‘reachable indices’ term is explained in the previous approach).
• Now for any current index, the minimum number of jumps required to reach any ‘reachable index’ from start(‘0’ th index) is minimum jumps required to reach this current ‘i’th index from start(‘0’ th index) + 1 (to reach index ‘i+x’ directly from index ‘i’) , that is,
  minJumps[i+x] = minJumps[i] + 1
  Where, x can be 1, 2, 3…A[i]
• Possibly We will be reaching the same index more than once with different number of jumps, but we want the minimum value, therefore, we update any minJumps[i] only if the current number of jumps required to reach ‘i’ is less then the current value at minJumps[i]

Time Complexity Discussion :
Again in this approach, from any index ‘i’ we are calculating minimum number of jumps of all the reachable indices by visiting all the reachable indices from any index, which can be ‘n’ in a worst case, and we are doing this for all n indices.
Therefore, the time complexity of this algorithm is O(n^2).

import java.util.Arrays;
 
public class minJumpsArr {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 0, 1, 1, 4 };
 
        int ans = solveDP(A);
        if(ans == Integer.MAX_VALUE)
        {
            /* if the min jumps for the last index is still infinity,
             * this means it has never been updated that is, we did
             * not reach the end index even once, hence answer is not
             * possible in this case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(ans);
        }
 
    }
 
    public static int solveDP(int[] a) {
        int[] minJumps = new int[a.length];
        /*
         * initialize min Jumps for every index to infinity
         * as the minimum value is to  be calculated for
         * every index
         */
        Arrays.fill(minJumps, Integer.MAX_VALUE);
        /* minimum jumps required to reach the very first index is zero */
        minJumps[0] = 0;
 
        /*calculating min jumps for every index */
        for (int i = 0; i < a.length; i++) {
            /* maximum length of jump from this index or the maximum
             * reachable index from this index*/
            int maxJump = a[i];
            for (int j = 1; j <= maxJump; j++) {
                /*visiting all the reachable index*/
                int reachableIdx = i + j;
                /* updating the minimum jumps required for every reachable
                 * index but only if the reachable index is in bounds and
                 * the intermediate index from which we are making jump to
                 * this reachable index must also be reachable from zeroth
                 * index*/
                if (reachableIdx < a.length && minJumps[i] != Integer.MAX_VALUE) {
                    /* min jumps for every reachable index is min jumps for this
                     * intermediate index 'i' + 1 ( for the jump from intermediate
                     * index to this reachable index) */
                minJumps[reachableIdx] = Math.min(minJumps[reachableIdx], minJumps[i] + 1);
                }
            }
        }
        /*finally return the minimum jumps required to reach last index*/
        return minJumps[a.length-1];
    }
 

Before moving on to the next approach, just think if we could do better by using a greedy approach and making greedy coices for next index to jump on, rather than exploring all the possibilities using Dynamic programming.

Approach – III :
Yes we can definitely solve the given problem more efficiently by adopting a greedy approach.

• The basic strategy would be to keep the track of Maximum reachable index the whole time which will eventually be updated frequently as we move through the given array and as soon as we reach this Maximum reachable index, we increment our number of jumps.
• For this, we maintain 2 variables which stores the value of current index and Maximum reachable index. The very first thing we do after reaching any index is update the value of Maximum reachable index by comparing it with current Index + A[current Index] (indicating the maximum length of any jump that can be made from here) and we upadate Maximum reachable index value if value of current Index + A[current Index] is greater than Maximum reachable index. That is,

MaxReachable = max( MaxReachable,  current Index + A[current Index])

• One point to reconsider is, What if after the updation of this Maximum reachable index its value is less than or equal to current Index?
  Well, this the case where we can not move from this current position and hence we can never reach the end index, therefore, in this case we simply return -1, indicating that no answer is possible in this case.

Now, we need to think about the correctness of our greedy approach again.

Can simply incrementing number of jumps when the value of current index is equal to max reachable index, always yield the correct answer everytime?

The answer would be a No, as max reachable index is getting updated and incremented by a value of A[current index] every time, this way value of current index can never be equal to max reachable index except for the case when the answer for a case isn’t possible.

• For making our approach perfect, we can take another variable which keeps the track of current reachable index, and instead of incrementing the value of jump when current index is equal to Max reachable index, we will increment jump when the current Index becomes equal to current reachable, and at this moment we update the current reachable to max reachable index also.

Time Complexity Discussion :
We visit every index exactly once and keep updating the declared variables as we traverse the given array having ‘n’ elements. Therefore, the worst time complexity of this algorithm is O(n) where n is the size of the given array.

public class minJumpsArr {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };
 
        int ans = jump(A);
        if(ans == -1)
        {
            System.out.println("Not Possible");
        }
        else {
            System.out.println("Minimum jumps required : " + ans);
        }
 
    }
 
    public static int jump(int[] a) {
        /*three variable as discussed in the editorial*/
        int maxReachable = 0;
        int jumps = 0;
        int currReachable = 0;
        /*exploring every index in the given array */
        for (int currIdx = 0; currIdx < a.length; currIdx++) {
 
            /*updating max reachable index every time we visit a new index*/
            maxReachable = Math.max(maxReachable, currIdx + a[currIdx]);
 
            /* as we have already considered the max jump length at this
             * index and if max reachable index is still equal to or
             * less than current index, then we can move forward from
             * this index therefore answer is not possible in this case*/
            if (maxReachable <= currIdx) {
                return -1;
            }
 
            /*if current index is equal to the current reachable, increment
             * jumps required and update current reachable*/
            if (currIdx == currReachable) {
                jumps++;
                currReachable = maxReachable;
            }
        }
        return jumps;
    }

That’s all about the Minimum Number of Jumps to reach last Index.