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:
Leave a Comment on this Post