Find minimum jumps required to reach the destination

Posted in

Find minimum jumps required to reach the destination
vinaykhatri

Vinay Khatri
Last updated on April 16, 2024

    You are given a list of positive numbers. In this list, each integer denotes the maximum number of jumps that you are able to make from that integer’s index to the forward direction. You need to determine the minimum number of jumps that you can make starting from the initial 0th index so that you can reach the end of the list. Please note that if an element is 0, you will not be able to make any further moves from that position.

    Sample Test Cases:

    Input: array[]={1, 3 ,5 ,8 ,9 ,3 ,4 ,5 ,6}
    
    Output: 3 [ 1->3-> 8/9->6]
    

    Explanation : Starting from the 1st element, we can jump from the 1st element to the 2nd element because only 1 jump is allowed. Now, from the 2nd element, i.e., 3, these are the choices of the number of jumps - 1, 2, 3. If we choose 2 or 3 jumps, then elements 8 and 9 can be reached from where we can easily reach the end of the array. So, the total number of jumps is 3.

    Input: array[]={1,1,1}
    Output: 3

    Explanation . All jumps have the same value, and at every position, a jump is needed, so the final jump is 3.

    Method 1: (Naive Approach)

    The Naive Approach is using a simple recursive approach to recursively call all the elements that can be possible to reach from the first element in the given array. So the minimum number of jumps to reach the end from the first element can be given as:

    MinimumJumps(starting position,ending position)=Minimum(minimumJumps(J,end), Where J represents all the possible jumps from the starting position.

    Java:

    //Importing libraries
    import java.util.*;
    import java.io.*;
    class MinJumps {
       //Function to return Maximum number of jumps to reach the end
       static int MinimumJumps(int array[], int start, int end)
       {
        //Handling the base cases checking whether the starting
        //Position equal to ending position
        if (end== start)
            return 0;
    
        //Return Maximum Value if position of particular index is zero
        if (array[start] == 0)
            return Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
          // Traverse  all the points from starting position recursively               
        // Get the minimum value possible value
        for (int i = start + 1; i <= end && i <= start + array[start];++i) {
             // Recursively call next possible position from ith position
            int jumps_total = MinimumJumps(array, i, end);
                // Calculating the minimum jumps   
            if (jumps_total != Integer.MAX_VALUE && jumps_total + 1 <min)
                min = jumps_total + 1;
        }
         // Return the minimum jumps to reach the end
        return min;
       }
    
       // Driver code of the program to Find the minimum possible jump
       public static void main(String args[])
       {
        // Array containing number of jumps for particular position
        int array[] = {1,2,5,2,4,7,8,9};
    
          // Length of the array
        int length_array = array.length;
        System.out.println("Total number of jumps to reach the end position " + MinimumJumps(array, 0, length_array - 1));
       }
    }
    

    Output

    C++

    #include <bits/stdc++.h>
    using namespace std;
    
    //Function to return the total number of jumps to reach the end position
    int MinimumJumps(int jumps_atpostion[], int n)
    {
       // Handling  the Base Case if the size of the
       // array is 1 Total number of jumps will be equal to zero
       if (n == 1)
           return 0;
    
       //Transverse all the possible position recursively from particular position index
       //Initialize  the minimum jumps
       int total_min_jumps = INT_MAX;
    
       for (int i = n - 2; i >= 0; --i) {
           if (i + jumps_atpostion[i] >= n - 1) {
               int min_jumpsatparticularposition = MinimumJumps(jumps_atpostion, i + 1);
               if (min_jumpsatparticularposition!= INT_MAX)
                   total_min_jumps = min(total_min_jumps, min_jumpsatparticularposition + 1);
           }
       }
       // Returning the total number of jumps possible to reach the end position
       return total_min_jumps;
    }
    
    // Driver Code of the program to Find the total number of jumps to reach  //the end
    int main()
    {
       int jumps_atpostion[] = {1,2,1,4,5,2,2,1};
    
       // Length of the array
       int length = sizeof(jumps_atpostion) / sizeof(jumps_atpostion[0]);
       cout << "Total number of jumps required to reach the end is : "<< MinimumJumps(jumps_atpostion, length)<<endl;
       return 0;
    }

    Output:

    Python:

    #Function to Find the minimum possible jumps to reach the end
    def MinimumJumps(array, starting, ending):
        # Handling Base Case if the starting index is equal to the ending index
        if (starting == ending):
            return 0
    
        # Checking if the jump at a particular position is zero if zero return maximum value 
        if (array[starting] == 0):
            return float('inf')  
    
        total_min_jumps = float('inf')
        for starting_index in range(starting + 1, ending + 1):
            if (starting_index < starting + array[starting] + 1):
                jump_at_particularPosition = MinimumJumps(array, starting_index, ending)
    
                # Updating the total_min_jumps
                if (jump_at_particularPosition != float('inf') and jump_at_particularPosition + 1 < total_min_jumps):
                    total_min_jumps = jump_at_particularPosition + 1
        return total_min_jumps
    
    # Driver program to Find the minimum Jumps to reach the end position
    array = [1, 3, 6, 3, 1, 3, 6, 8, 9, 5]
    
    # Length of the array
    n = len(array)
    print('Total number of jumps to reach the end position', MinimumJumps(array, 0, n-1))

    Output:

    Complexity :

    • Time Complexity : O(n^n). There are maximum n possible moves from the particular element. So, the upper bound for the complexity of this program is O(n^n).
    • Auxiliary Space: The Auxiliary Space Complexity of this program is O(1) if we ignore the stack space. Otherwise, the Space Complexity of this program will be O(n) because of the stack space in every recursive call in each step.

    Note : Above approach is a time-consuming approach and not an optimized approach because there are many cases when one subproblem is called one or more times. Hence there will be overlapping subproblems. For example, Minimumjump(3, 6) will be called two times as array[3] can be called from array[1] and array[2]. There are two methods (tabular and memoization) to overcome this problem, both of which use, Dynamic programming.

    Method 2 - (Tabular):

    Dynamic Programming is the optimization of recursion. In the above, we encounter many overlapping problems. We can optimize this using Dynamic Programming. The idea is simply to store the answer to the subproblems so that we do not recompute a particular subproblem whenever we encounter any function call. This simple approach reduces the time complexity of the program from exponential to polynomial.

    Approach:

    1. We make jumps [] array in which i’th index of the jumps[i’th] indicates the minimum jump to reach jumps[i] from the jump[0] position.
    2. Fill the jumps[0] to 0.
    3. The outer loop runs from 1 to n-1, and the inner loop from 0 to n-1.
    4. Initially, set jumps[i] to INT MAX. If i is less than j + array[j], then set jumps[i] to minimum of jumps[i] and jumps[j] + 1.
    5. Finally, return the jumps[n-1] that is the total minimum jump.

    JAVA:

    import java.util.*;
    import java.io.*;
    class Main {
     
        private static int TotalNumberofJumps(int[] jumps_array, int length)
        {
            //Creating jumps array to store the minimum jumps at particular position
            int jumps_at_postion[] = new int[length];
            // result
            int i, j;
             //Handling the base case if the jump at particular position is zero or not
            if (length == 0 || jumps_array[0] == 0)
                return Integer.MAX_VALUE;
            
            //Initialize the minimum jump at position 0 is zero 
            jumps_at_postion[0] = 0;
     
            //Find the minimum number of jumps to reach arr[i] from arr[0]
            for (i = 1; i < length; ++i) {
                jumps_at_postion[i] = Integer.MAX_VALUE;
                for (j = 0; j < i; ++j) {
                    if (i <= j + jumps_array[j]
                        && jumps_at_postion[j]
                            != Integer.MAX_VALUE) {
                           // Storing the min jumps to reach at position i
                                jumps_at_postion[i] = Math.min(jumps_at_postion[i], jumps_at_postion[j] + 1);
                        break;
                    }
                }
            }
            //Returning the Total number of jumps to reach the end position
            return jumps_at_postion[length-1]; 
        }
     
        // Driver program to Find the total number of Jumps to reach the end
        public static void main(String[] args)
        {
            // Array containing the maximum jumps possible at particular   position
            int Jump_array[] = {1, 3, 6, 3, 1, 3, 6, 8, 9, 5};
     
            System.out.println("Total Number of jumps to reach the end position : "
                            + TotalNumberofJumps(Jump_array, Jump_array.length));
        }
    }

    Output:

    Python:

    #Function to Find Total number of  jumps to reach the end position 
    def Minimum_jumps(jump_array, n):
        jumps_at_position = [0 for i in range(n)]
        #Handling the base Cases if the jump at particular position is zero   or not
        if (n == 0) or (jump_array[0] == 0):
           return float('inf')
        #Initialise the jumps array at position 0 to 0
        jumps_at_position[0] = 0
     
        #Find the minimum number of jumps need to reach jumps[i] from jumps[0]
        for i in range(1, n):
            jumps_at_position[i] = float('inf')
            for j in range(i):
                if (i <= j + jump_array[j]) and (jumps_at_position[j] != float('inf')):
                    #Storing the Minimum jump to reach at position i
                    jumps_at_position[i] = min(jumps_at_position[i], jumps_at_position[j] + 1)
                    break
        return jumps_at_position[n-1]
     
    # Driver Program to Find the total number of jumps to reach the end position
    jump_array = [1, 3, 6, 3, 1, 3, 6, 8, 9, 5]
    size = len(jump_array)
    print('Total Number of jumps to reach the end position',  Minimum_jumps(jump_array,size))

    Output:

    C++

    //Importing libraries
    #include <bits/stdc++.h>
    using namespace std;
    
    int min(int a, int b) 
        { return (a < b) ? a : b; }
    
    //Function to return the minimum number of jumps
    int MinimumJumps(int jump_array[], int length)
        {
          //Creating jumps array to store the minimum jumps at particular position
          int* jumps_at_position = new int[length];
          int i, j;
          
          //Creating jumps array to store the minimum jumps at particular position
          if (length == 0 || jump_array[0] == 0)
               return INT_MAX;
          //Initialize the minimum jump at position 0 is zero
          jumps_at_position [0] = 0;
    
          // Finding the minimum jumps to reach jumps[i] from jumps[0]
          for (i = 1; i < length; ++i) {
               jumps_at_position [i] = INT_MAX;
               for (j = 0; j < i; ++j) {
                   if (i <= j + jump_array[j] && jumps_at_position [j] != INT_MAX) {
                        // Storing the min jumps to reach at position i
                        jumps_at_position [i] = min(jumps_at_position [i], jumps_at_position [j] + 1);
                        break;
                           }
                     }
                 }
            //Returning the Total number of jumps to reach the end position
            return jumps_at_position[length - 1];
       }
    
    // Driver code of the program to find the minimum possible jumps
    int main()
    {
        // Array containing the maximum jumps possible at particular position
        int jump_array[] =  {1, 3, 6, 3, 1, 3, 6, 8, 9, 5};
    
         // length of the array
         int length = sizeof(jump_array) / sizeof(int);
         cout << "Total Number of jumps to reach the end position "
             << MinimumJumps(jump_array, length)<<endl;
         return 0;
    }

    Output:

    Complexity:

    • Time complexity : O(n^2). Because a nested traversal of the array is needed.
    • Auxiliary Space :O(n). To store the DP array, we need O(n) space.

    Method 3: (Memoization)

    The memoization Approach is the extension of the recursion approach with some variation in recursion. The main disadvantage of the recursion is there are many overlapping causes like Minimumjumps(3, 9) that will be called two times as array[3] can be reached from array[1] and array[2]. So, we generally store the answer to subproblems in an array and return the answer of that subproblem that whenever we encounter a particular subproblem in any other function call. This process speeds up the program and increases the efficiency of the code.

    JAVA:

    import java.util.*; 
    import java.io.*;
    class Main
    {
        //Function to Find total number of jumps need to reach the end position 
        public static int Minimum_jumps(int[] jumps_array, int starting_index, int length, int[] dp)
        {
            //Base Case if starting index reach to the ending index
            if (starting_index == length - 1) {
                return 0;
            }
            //Handling the base Cases if the jump at particular position is zero   or not
            if (starting_index >= length || jumps_array[starting_index] == 0) {
                return Integer.MAX_VALUE;
            }
            //Checking whether the particular recursive call answer exists in the array or not
            if (dp[starting_index] != 0) {
                return dp[starting_index];
            }
     
            
            int minjumps = Integer.MAX_VALUE;
            for (int j = starting_index + 1; j <= starting_index + jumps_array[starting_index]; ++j)
            {   
                //Recursively call to the next possible jump from ith index
                int min_jumps_particularindex = Minimum_jumps(jumps_array, j, length, dp);
                if ( min_jumps_particularindex != Integer.MAX_VALUE) {
                    minjumps = Math.min(minjumps,  min_jumps_particularindex+ 1);
                }
            }
     
            // Storing the recursive call answer if not present in the dp array
            return (dp[starting_index] = minjumps);
        }
        //Driver code to Find the total number of jumps to reach the end position
        public static void main(String[] args)
        {
            int[] jumps_at_particular_position = { 1, 3, 6, 1, 0, 9 };
     
            //Array to store the recursive call answer i.e memoization
            int[] dp = new int[jumps_at_particular_position.length];
     
            System.out.println("Total number of jumps to reach the end position is " +Minimum_jumps(jumps_at_particular_position ,0, jumps_at_particular_position.length, dp));
        }
    }

    Output:

    C++:

    #include <bits/stdc++.h>
    using namespace std;
    
    //Function to Find the Minimum of two numbers
    int minjumps(int a, int b) { return (a < b) ? a: b; }
    
    //Function to find total number of jumps to reach the end position
    int MinimumJumps(int jump_array[], int starting_index, int ending, int Min_jumps_value_atposition[])
    {
       if (starting_index == ending - 1) {
           return 0;
       }
    
        //Handling the base Cases if the jump at particular position is zero   or not
       if (starting_index  >= ending || jump_array[starting_index] == 0) {
           return INT_MAX;
       }
       //Checking whether the particular recursive call answer exits in the array or not
       if ( Min_jumps_value_atposition[starting_index] != 0){
           return Min_jumps_value_atposition[starting_index];
       }
       int Minjumpsatposition = INT_MAX;
       for (int j = starting_index + 1; j <= starting_index + jump_array[starting_index]; j++)
       {
           int min_jumps_particularindex = MinimumJumps(jump_array, j, ending, Min_jumps_value_atposition);
           if (min_jumps_particularindex != INT_MAX) {
                Minjumpsatposition = minjumps( Minjumpsatposition, min_jumps_particularindex + 1);
           }
       }
       // if the subproblem is seen for the first time
       return (Min_jumps_value_atposition[starting_index] = Minjumpsatposition);
    }
    
    int main( )
    {
       int array[] = { 1, 3, 6, 1, 0, 9};
       int length = sizeof(array) / sizeof(array[0]);
       // Creating an array to store the total jump at particular position
       int jumps[length];
       memset(jumps, 0, length * sizeof(int));
       printf("Total Number of jumps to reach the ending position %d\n" ,MinimumJumps(array, 0, length, jumps));
       return 0;
    }

    Output

    Python:

    import sys
    
    #Function to Find Total_number_of_jumps to reach the end position
    def findMinJumps(A, starting_index, length, dp):
        # Checking base check if starting_index is equal to the ending index or not
        if starting_index == length - 1:
            return 0
    
        #Checking whether the jump at particular index is zero or not
        if starting_index >= length or A[starting_index] == 0:
            return sys.maxsize
        # if the answer of particular recursive call exists in the array or not
        if dp[starting_index]:
            return dp[starting_index]
        # Find the minimum jump to reach the end position and store in the min_jumps
        min_jumps = sys.maxsize
        for j in range(starting_index + 1, starting_index + A[starting_index] + 1):
            cost = findMinJumps(A, j, length, dp)
            if cost != sys.maxsize:
                min_jumps = min(min_jumps, cost + 1)
        # if the recursive call occurs first time store the answer
        dp[starting_index] = min_jumps
        return dp[starting_index]
    
    jump_array = [1, 3, 6, 1, 0, 9]
    #Create an array to store the recursive call answers
    dp = [0] * len(jump_array)
    print("The minimum jumps required to reach the destination are",
           findMinJumps(jump_array, 0, len(jump_array), dp))

    Output:

    Complexity:

    • Time complexity : O(n^2). Because a nested traversal of the array is needed.
    • Auxiliary Space : O(n). To store the DP array, we need O(n) space.

    Conclusion

    Finding minimum jumps required to reach the destination is one of the most famous problems of Dynamic Programming. There are many variations that exist for this problem as well. In this article, we have discussed three approaches to solve this problem. The Naive Approach, i.e., a simple recursion, the other is the optimized approach, i.e., Memoization, and the third one is the Dynamic Programming approach which is the most optimized approach.

    The optimized approach overcomes the overlapping recursive calls which are present in the Naive Approaches. That’s why we generally prefer DP and Memoization instead of plain recursion when we have large constraints. We certainly hope that this article will help you understand this problem in greater detail.

    Happy Learning!

    People are also reading:

    Leave a Comment on this Post

    0 Comments