Minimum number of jumps to reach end | GeeksforGeeks

Related: LeetCode 45 - Jump Game II
LeetCode 55 - Jump Game
Minimum number of jumps to reach end | GeeksforGeeks
Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)

First element is 1, so can only go to 3. Second element is 3, so can make at most 3 steps eg to 5 or 8 or 9.

Method 1 (Naive Recursive Approach)

A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.

minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start

int minJumps(int arr[], int l, int h)

{

   // Base case: when source and destination are same

   if (h == l)

     return 0;

   // When nothing is reachable from the given source

   if (arr[l] == 0)

     return INT_MAX;

   // Traverse through all the points reachable from arr[l]. Recursively

   // get the minimum number of jumps needed to reach arr[h] from these

   // reachable points.

   int min = INT_MAX;

   for (int i = l+1; i <= h && i <= l + arr[l]; i++)

   {

       int jumps = minJumps(arr, i, h);

       if(jumps != INT_MAX && jumps + 1 < min)

           min = jumps + 1;

   }

   return min;

}

Method 2 (Dynamic Programming) - O(N^2)
In this method, we build a jumps[] array from left to right such that jumps[i] indicates the minimum number of jumps needed to reach arr[i] from arr[0]. Finally, we return jumps[n-1].

int minJumps(int arr[], int n)

{

    int *jumps = new int[n];  // jumps[n-1] will hold the result

    int i, j;

    if (n == 0 || arr[0] == 0)

        return INT_MAX;

    jumps[0] = 0;

    // Find the minimum number of jumps to reach arr[i]

    // from arr[0], and assign this value to jumps[i]

    for (i = 1; i < n; i++)

    {

        jumps[i] = INT_MAX;

        for (j = 0; j < i; j++)

        {

            if (i <= j + arr[j] && jumps[j] != INT_MAX)

            {

                 jumps[i] = min(jumps[i], jumps[j] + 1);

                 break;

            }

        }

    }

    return jumps[n-1];

}

Method 3 (Dynamic Programming)
In this method, we build jumps[] array from right to left such that jumps[i] indicates the minimum number of jumps needed to reach arr[n-1] from arr[i]. Finally, we return arr[0]

int minJumps(int arr[], int n)

{   

    // jumps[0] will hold the result

    int *jumps = new int[n]; 

    int min;

  

    // Minimum number of jumps needed 

    // to reach last element from last

    // elements itself is always 0

    jumps[n-1] = 0;

  

  

    // Start from the second element, 

    // move from right to left and 

    // construct the jumps[] array where

    // jumps[i] represents minimum number

    // of jumps needed to reach 

    // arr[m-1] from arr[i]

    for (int i = n-2; i >=0; i--)

    {

        // If arr[i] is 0 then arr[n-1] 

        // can't be reached from here

        if (arr[i] == 0)

            jumps[i] = INT_MAX;

  

        // If we can direcly reach to 

        // the end point from here then

        // jumps[i] is 1

        else if (arr[i] >= n - i - 1)

            jumps[i] = 1;

  

        // Otherwise, to find out the minimum

        // number of jumps needed to reach 

        // arr[n-1], check all the points 

        // reachable from here and jumps[] 

        // value for those points

        else

        {   

            // initialize min value

            min = INT_MAX; 

  

            // following loop checks with all

            // reachable points and takes 

            // the minimum

            for (int j = i + 1; j < n && j <= 

                             arr[i] + i; j++)

            {

                if (min > jumps[j])

                    min = jumps[j];

            }     

  

            // Handle overflow 

            if (min != INT_MAX)

            jumps[i] = min + 1;

            else

            jumps[i] = min; // or INT_MAX

        }

    }

  

    return jumps[0];

}

https://www.geeksforgeeks.org/minimum-number-jumps-reach-endset-2on-solution/

Variables to be used:

1. maxReach The variable maxReach stores at all time the maximal reachable index in the array.
2. step The variable step stores the number of steps we can still take(and is initialized with value at index 0,i.e. initial number of steps)
3. jump jump stores the amount of jumps necessary to reach that maximal reachable position.

Given array arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9

• maxReach = arr[0]; // arr[0] = 1, so the maximum index we can reach at the moment is 1.
  step = arr[0]; // arr[0] = 1, the amount of steps we can still take is also 1.
  jump = 1; // we will always need to take at least one jump.
• Now, starting iteration from index 1, the above values are updated as follows:
  1. First we test whether we have reached the end of the array, in that case we just need to return the jump variable.

     if (i == arr.length - 1)
         return jump;
     

  2. Next we update the maxReach. This is equal to the maximum of maxReach and i+arr[i](the number of steps we can take from the current position).

     maxReach = Math.max(maxReach,i+arr[i]);
     

  3. We used up a step to get to the current index, so steps has to be decreased.

     step--;
     

  4. If no more steps are remaining (i.e. steps=0, then we must have used a jump. Therefore increase jump. Since we know that it is possible somehow to reach maxReach, we again initialize the steps to the number of steps to reach maxReach from position i. But before re-initializing step, we also check whether a step is becoming zero or negative. In this case, It is not possible to reach further.

     if (step == 0) {
         jump++;
         if(i>=maxReach)
            return -1;
         step = maxReach - i;
     }

    static int minJumps(int arr[])

    {

        if (arr.length <= 1)

            return 0;

  

        // Return -1 if not possible to jump

        if (arr[0] == 0)

            return -1;

  

        // initialization

        int maxReach = arr[0];

        int step = arr[0];

        int jump = 1;

  

  

        // Start traversing array

        for (int i = 1; i < arr.length; i++)

        {

            // Check if we have reached the end of the array

            if (i == arr.length - 1)

                return jump;

  

            // updating maxReach

            maxReach = Math.max(maxReach, i+arr[i]);

  

            // we use a step to get to the current index

            step--;

  

            // If no further steps left

            if (step == 0)

            {

                //  we must have used a jump

                jump++;

                   

                //Check if the current index/position  or lesser index

                // is the maximum reach point from the previous indexes

                if(i>=maxReach)

                   return -1;

  

                // re-initialize the steps to the amount

                // of steps to reach maxReach from position i.

                step = maxReach - i;

            }

        }

  

        return -1;

    }