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:
- 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.
- Fill the jumps[0] to 0.
- The outer loop runs from 1 to n-1, and the inner loop from 0 to n-1.
- 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.
- 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:
- Find and remove loops in a Linked List
- Find a Pair with the Given Sum in an Array
- Data Structure Interview Questions
- Data Structure & Algorithm: Interpolation Search
- What is Structured Programming?
- Tree Traversal
- AVL Tree
- DSA: Binary Heap Tree
- DSA: Program for Tower of Hanoi
- Circular Doubly Linked List
Leave a Comment on this Post