For more clarity of the question, watch part of the video.
Approach
In this problem we need to find all the paths which use a minimum number
of jumps.
So to solve this problem, first of all we will build a dp and then we will
reverse engineer this using BFS (Breadth First Search). However this
problem can be solved using BFS and DFS.
At element n1, we have n1 options to take jumps of lengths less than or
equal to the value of n1.
For example, let's consider sample input.
At the first element i.e. 3 (index 0), we have 3 options to take jumps and
that is of lengths 1 or 2 or 3.
Choice-1 (C1) : Choosing option 1; our length of jump becomes 1, this
means using this option we will reach the second element (i.e. 3 at index 1).
Choice-2 (C2) : Choosing option 2; our length of jump becomes 2, this
means using this option we will reach the second element (i.e. 0 at index 2).
Choice-3 (C3) : Choosing option 3; our length of jump becomes 3, this
means using this option we will reach the second element (i.e. 2 at index 3).
Similarly at fourth element i.e. 2 (index 3), we will have 2 options to take
jumps and that is of lengths 1 or 2.
Choice-1 (C1) : Choosing option 1; our length of jump becomes 1, this
means using this option we will reach the fifth element (i.e. 1 at index 4).
Choice-2 (C2) : Choosing option 2; our length of jump becomes 2, this
means using this option we will reach the sixth element (i.e. 2 at index 5).
Basic Premise:
So the basic premise which we use to solve this problem is that suppose if
we are at a source (s) and we need to reach a destination (d).
And we have s options to reach intermediate stages say i1, i2 and i3.
Then we will choose that intermediate stage from which we can reach the
destination with minimum jumps.
Say that in this case you can reach the destination d in 4 jumps from i1, 2
jumps from i2 and 3 jumps from i3.
As reaching any intermediate stage will take 1 jump so if we choose i1 then
we can reach the destination in 5 jumps, if we choose i2 then we can reach
the destination in 3 jumps and if we choose i3 then we can reach the
destination in 4 jumps.
And among all these options, choosing i2 gives us the minimum number of
jumps i.e. 3 to reach the destination d.
Steps:
First of all we will assign storage and meaning.
After that we will give direction to the problem.
Finally we need to travel and solve the problem.
Building solution:
So to assign storage and meaning to the problem, we will take an array of
size N, which will store the minimum number of jumps required to reach
the destination from the element present at the corresponding index in the
input array.
Then we see that to reach the destination from the last element we don't
need to take any steps (i.e. 0), so we store 0 corresponding to this last
element in the jumps array. And we call this smallest problem. The biggest
problem will be to calculate the minimum jumps from the first element
(source) which is 3 in this case.
So to solve the problem we will travel from smallest problem to biggest
problem and simultaneously fill our jump array (i.e. we will travel the
jump array in reverse order).
Let's apply the above rules to the input array. We start to fill our
corresponding jump array for this input in the reverse order:
We put 0 corresponding to the last element without thinking twice as
we discussed that we don't need to take any more jumps to reach the
destination from the last element as we are already at the destination.
Then we move to 0 (at index 8). 0 indicates that we have 0 options to
choose to take some jumps. So we will put a null corresponding to this
0 in the jump array.
Then we move to 2 (at index 7). 2 indicates that we have 2 options to
take jumps and that is of lengths 1 or 2.
Choosing option 1; our length of jump becomes 1, this means using this
option we will reach the element 0 (at index 8).
Choosing option 2; our length of jump becomes 2, this means using this
option we will reach the element 0 (at index 9).
Option 1 is not valid because using option 1 we reach 0 at index 8 and
from this index we have no way to reach our destination. So we are left
with option 2.
Choosing option 2 is valid as we directly reach the destination (i.e. 0 at
index 9).
So we store 1 corresponding to 2 (at index 7). As we directly reached
the destination using option 2 from 2 (at index 7).
Now we move to 4 (at index 6). 4 indicates that we have 4 options to
take jumps and that is of length 1 or 2 or 3 or 4.
Choosing option 1; our length of jump becomes 1, this means using this
option we will reach element 2 (at index 7).
Choosing option 2; our length of jump becomes 2, this means using this
option we will reach the element 0 (at index 8).
Choosing option 3; our length of jump becomes 3, this means using this
option we will reach the element 0 (at index 9) which is also the
destination.
Option 4 will be invalid as it will take us out of the array.
In this case it is obvious that choosing option 3 is the best choice as we
will directly reach the destination without any intermediate stage.
So we store 1 corresponding to 4 (at index 6). As we directly reached
the destination using option 3 from 4 (at index 6).
Now we move to 2 (at index 5). 2 indicates that we have 2 options to
take jumps and that is of length 1 or 2.
Choosing option 1; our length of jump becomes 1, this means using this
option we will reach the element 4 (at index 6).
Choosing option 2; our length of jump becomes 2, this means using this
option we will reach element 2 (at index 7).
We have 1 stored corresponding to both 4 (index 6) and 2 (index 7)
which implies that choosing either way will lead to taking 1 step more
from both of them to reach the destination.
So we need to add 1 to the jump stored corresponding to 4 or 2 (1) as
we need to take a step from 2 (at index 5) to either reach 4 (index 6) or
2 (at index 7), that make the count of jump to 2 which we store
corresponding to 2 (at index 5) in jump array.
Now we move to 1 (at index 4). 1 indicates that we have only 1 option
to take jumps and that is of length 1.
Choosing this only option; our length of jump becomes 1, this means
using this option we will reach element 2 (at index 5).
So we simply add 1 to the count of jump stored corresponding to 2 (at
index 5 and 2 is number of jumps stored corresponding to this 2) as we
need to take a step from 1 (at index 4) to reach 2 (index 5), that make
the count of jump to 3 which we store corresponding to 1 (at index 4)
in jump array.
Now we move to 2 (at index 3). 2 indicates that we have 2 options to
take jumps and that is of length 1 or 2.
Choosing option 1; our length of jump becomes 1, this means using this
option we will reach element 1 (at index 4).
Choosing option 2; our length of jump becomes 2, this means using this
option we will reach element 2 (at index 5).
We have 3, stored corresponding to 1 (index 4) and 2 stored
corresponding to 2 (index 5) which implies that choosing option 2 is
more efficient as it needs less number of jumps to reach the destination
using this option.
So we store 1 plus the minimum count among these which is 2 in this
case making the count for element 2 (index 3) to be 3.
Then we move to 0 (at index 2). 0 indicates that we have 0 options to
choose to take some jumps. So we will put a null corresponding to this
0 in the jump array.
Then we move to 3 (at index 1). 3 indicates that we have 3 options to
take jumps and that is of lengths 1 or 2 or 3.
Choosing option 1; our length of jump becomes 1, this means using this
option we will reach the element 0 (at index 2).
Choosing option 2; our length of jump becomes 2, this means using this
option we will reach element 2 (at index 3).
Choosing option 3; our length of jump becomes 3, this means using this
option we will reach element 1 (at index 4).
Option 1 is not valid because using option 1 we reach 0 at index 2 and
from this index we have no way to reach our destination. So we are left
with option 2 and 3.
We have 3, stored corresponding to both 2 (index 3) and 1 (index 4)
which implies that choosing either way will lead to taking 1 step more
from both of them to reach the destination.
So we need to add 1 to the jump stored corresponding to 2 or 1 (3) as
we need to take a step from 3 (at index 1) to either reach 2 (index 3) or
1 (at index 4), that make the count of jump to 4 which we store
corresponding to 3 (at index 1) in jump array.
Then we move to 3 (at index 0). 3 indicates that we have 3 options to
take jumps and that is of lengths 1 or 2 or 3.
Choosing option 1; our length of jump becomes 1, this means using this
option we will reach the element 3 (at index 1).
Choosing option 2; our length of jump becomes 2, this means using this
option we will reach the element 0 (at index 2).
Choosing option 3; our length of jump becomes 3, this means using this
option we will reach element 2 (at index 3).
Option 2 is not valid because using option 2 we reach 0 at index 2 and
from this index we have no way to reach our destination. So we are left
with option 1 and 3.
We have 4 stored corresponding to 3 (index 1) and 3 stored
corresponding to 2 (index 3) which implies that choosing option 2 is
more efficient as it needs less number of jumps to reach the destination
using this option.
So we store 1 plus the minimum count among these which is 3 in this
case making the count for element 3 (index 0) to be 4.
And we are finally done. Our final count of jumps is stored at index 0 in
array jump. (as at index 0 it means that number of minimum jumps
with which we can reach the destination from source which is element
at 0 th index)
So we have found the minimum number of jumps with which we can reach the
destination. But we are not done yet.
For more clarity of this part; watch part of the video.
Now we need to print the path which we can choose using these jumps.
This time we will travel the array in increasing order of indices. We start
from the 0th index, 4 is stored in the jump array corresponding to this 3.
Also we keep track of the value of index, size which is equal to the value of
the element, jumps which represents the minimum number of jumps
corresponding to the element at the same index in the jump array and
lastly we maintain a string asf (answer so far) which will store the path. We
will store all these values in a pair and also use a queue.
Initially index is 0, size is 3, jumps are 4 and we append 3 in asf, so we
make a new pair and add all the information to it.
Now to get the path we look for the next 3 elements (equal to the value of
element) and find the ones which have 3 stored in the jump array
corresponding to these elements.
We can check this using a loop which runs for size times. In this case 3 is
only stored corresponding to element 2 at index 3.
So we add a new pair with index i to 3, size to 2, and jump to 3 and add 2 to
the asf.
Now we will apply a loop on 2 and check the next 2 elements and check
which has jumped one less (i.e. 2) than the jumps of 2 (i.e. 3). We find that
the 2 at index 5 has 2 jumps.
So we add a new pair with index i to 5, size to 2, and jump to 2 and add 2 to
the asf.
Now we will apply a loop on 2 and check the next 2 elements and check
which has jumped one less (i.e. 1) than the jumps of 2 (i.e. 2). We find that
both the elements next to this 2 have 1 stored as jumps so we need to
explore both the elements i.e. 4 at index 6 and 2 at index 7.
First, we will explore 4 at index 6.
To explore paths via 4, we add a new pair to the queue with index i to 6,
size to 4, and jump to 1 and add 4 to the asf.
Then we will apply a loop on 4 and check the next 4 elements and check
which jump is one less (i.e. 0) than the jumps of 4 (i.e. 1). We find that the 0
at index 9 has 0 stored as jumps. Also the for loop will run only 3 times in
this case as for the last iteration, the value of index will be out of bound.
So we add a new pair to the queue with index i to 9, size to 0, and jump to 0
and add 0 to the asf.
As we have reached the end of the loop, we will print the asf.
Now we will explore the 2 nd path from 2 (at index 5).
To explore the 2nd path via 2 (at index 7), we update the index i to 6, size
to 4, and jump to 1 and add 4 to the asf.
Then we will apply a loop on 2 and check the next 2 elements and check
which has jumped one less (i.e. 0) than the jumps of 2 (i.e. 1). We find that
the 0 at index 9 has 0 stored as jumps.
So we add a new pair to the queue with index i to 9, size to 0, and jump to 0
and add 0 to the asf.
As we have reached the end of the loop, we will print the asf.
For more clarity of this part; watch part of the video.
Let's try to code this!
public static void minJumps(int []arr){
int dp[] = new int[arr.length]; //1
// dp[arr.length-1] = ;
for(int idx = arr.length-2 ; idx >=0 ; idx--){ //2
int steps = arr[idx]; //3
int min = Integer.MAX_VALUE; //4
if(steps > 0){ //5
for(int i = 1 ; i <= steps ;i++){ //6
if(idx + i < arr.length) //7
min = Math.min(min,dp[idx+i]); //8
}
}
dp[idx] = min == Integer.MAX_VALUE ? min : min+1; //9
}
System.out.println(dp[0]); //10
minJumpRE(arr, dp); //11
}
java;
true";
First of all we define a dp array which will be used to store the
minimum number of jumps corresponding to the element at the same index in
the input array arr.
After that we apply a reverse loop on the arr and travel the array.
-Then we define a variable step which will store the value of the
element at index idx.
Then define a min variable and initialize it with INTEGER.MAX VALUE.
Now we check if the value stored in steps is positive. We proceed
further only if its positive value, because a negative value implies that we
cannot move and make a jump in the same direction.
-Then we run a for loop for steps number of times to get the minimum
number of jumps from idxth position of array arr.
Then we check if idx + i is less than array arr's length because
otherwise we will get an index out of bound error.
Then we update min with the minimum among min and value at idx + i
in dp array.
After getting out of the nested for loop we update the value at idx in dp
array with the min+1 if the min is no more the INTEGER.MAX VALUE (because
in that case it means that there is no way to reach destination).
After completely filling our dp array we will print the value at dp[0]
which will be storing the minimum number of jumps needed to reach the
destination from source i.e. to the last index from the first index.
public static class Pair{ //1
int idx;
String asf;
int jmps;
Pair(int idx,String asf,int jmps){ //2
this.idx = idx;
this.asf = asf;
this.jmps = jmps;
}
}
java;
true";
We create a class Pair with its data members as idx (index), asf
(answer so far) and jmps (jumps).
After that we add a pair to the queue with idx as 0, an empty asf string
and jump as the jumps corresponding to the 0th element of array.
Then we apply a while loop until the queue empties out.
Then we remove a pair from the queue and store it in a variable tmp.
Then we check if the jumps of pair tmp equal to zero.
If yes, then we simply print the asf.
And then continue.
Otherwise the control enters the for loop and runs for the value times
of the element stored in array at tmp's index.
Then we check if tmp's idx plus step is less than arr.length and one less
in tmp's jmps is equal to dp[tmp.idx+step] is true or not.
After that add a new pair to the queue by updating asf from tmp.
For more clarity of the code, watch part of the video.
Complexities:
Time Complexity: O(n)
A for loop is used 2 times, which condenses to O(n).
Space Complexity: O(n)
One n sized arrays are used which condense to O(n).
Complete Code:
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main{
public static class Pair{
int idx;
String asf;
int jmps;
Pair(int idx,String asf,int jmps){
this.idx = idx;
this.asf = asf;
this.jmps = jmps;
}
}
public static void minJumpRE(int []arr,int []dp){
Queue<Pair> queue = new ArrayDeque<>();
queue.add(new Pair(0 , ""+ 0 , dp[0]));
while(queue.size() > 0){
Pair tmp = queue.remove();
if(tmp.jmps == 0){
System.out.println(tmp.asf+" .");
continue;
}
for(int step = 1 ; step <= arr[tmp.idx] ; step++){
if(tmp.idx+step < arr.length && tmp.jmps-1 == dp[tmp.idx+step]){
queue.add(new Pair(tmp.idx+step, tmp.asf +" -
> " + (tmp.idx+step), tmp.jmps-1));
}
}
}
}
public static int[] minJumps(int []arr){
int dp[] = new int[arr.length];
// dp[arr.length-1] = ;
for(int idx = arr.length-2 ; idx >=0 ; idx--){
int steps = arr[idx];
int min = Integer.MAX_VALUE;
if(steps > 0){
for(int i = 1 ; i <= steps ;i++){
if(idx + i < arr.length)
min = Math.min(min,dp[idx+i]);
}
}
dp[idx] = min == Integer.MAX_VALUE ? min : min+1;
// System.out.print(dp[idx]+" ");
}
return dp;
}
public static void Solution(int arr[]){
int dp[] = minJumps(arr);
System.out.println(dp[0]);
minJumpRE(arr, dp);
}
public static void main(String []args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int arr[] = new int[n];
for(int i = 0 ; i < n ; i++)
arr[i] = scn.nextInt();
Solution(arr);
scn.close();
}
}
java;
true";
We hope that this article was helpful. If somehow you are finding it difficult to
understand this problem then we advise you to watch our video lecture of this
problem.
Trust me it will just get easier to understand after you have watched the
solution video.
You can contact us via our website. Doubts, suggestions and feedback are
always welcomed.
It is also advised that you follow the sequence of modules and questions
which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step
of each problem.
