Hey coder. We are going to discuss the problem "Frog Jump" in this article. Doesn't it sound interesting?
But before moving further you should go through the problem to understand its outline.
Important Links : Problem Link, Solution Video
Prev Next
FROG JUMP
Problem Discussion
- You are given an array of positive integers in ascending order, which represents the position of stones in the river.
- A frog is trying to cross a river. It can jump on a stone, but it must not jump into the water.
- You have to find if the frog can cross the river by landing on the last stone.
- The frog is on the first stone initially, and from the first stone it can jump 1 unit only.
- The frog can only jump k-1, k, or k+1 units in the forward direction, where k is the frog's last jump.
Let us understand this problem for the input array [0,1,3,5,6,8,12,17]. According to this array, the stones are placed as shown in figure 1.
We need to find if the frog is originally at 0th stone, will it be able to reach the 17th stone.
Let's figure out how the frog must jump.
- When the frog is at 0th stone then according to the question it can jump by 1 unit only and hence reaches the 1st stone.
- On reaching the 1st stone, the frog has 3 options, to jump by k-1=0 or k=1 or k+1=2 units. We know that jumping by 0 units is not really an option because it needs to move forward.
If the frog jumps by 1 unit, it will fall in the water. But on jumping 2 steps it will reach the 3rd stone. - Since the last jump was of 2 units, therefore k=2. On reaching 3rd stone, the frog can jump by k-1=1 or k=2 or k+1=3 units.
On jumping by 1 unit, 2 units and 3 units, the frog will, fall in the water, step on the 5th stone and step on the 6th stone respectively. - Now, we have 2 options. Either the frog can take a jump of k=2 and reach the 5th stone from which it can further take k-1=1 or k=2 or k+1=3 steps. Or the frog can take a jump of k=3 and reach the 6th stone from which it can further take k-1=2 or k=3 or k+1=4 steps.
APPROACH 1
- From the above discussion we realize that we need to store the number of jumps that can be taken from each stone. This is done using a HashMap.
In figure 5, against stone 0, we store that 1 jump can be made. Similarly values are to be stored against every stone. - For the 0th stone, a jump of 1 unit is applied. Hence k=1 and we can now find the possible jumps for 1st stone i.e. 0, 1 and 2. We do not include a jump of 0 units in the HashMap.
- Now for the 1st stone, if a jump of 1 unit is applied, the frog falls in the water. Hence the desirable last jump is k=2 by which we reach the 3rd stone. Hence the possible jumps for 3rd stone are k-1=1, k=2 and k+1=3.
- For the 3rd stone, as previously discussed we can either reach stone 5 or stone 6. Hence, we list the options for k=2 as well as k=3. Therefore possible jumps for stone 5 are 1, 2 and 3 and for stone 6 are 2, 3 and 4.
- Similarly, by adding 1, 2 and 3 jumps from stone 5, we reach stone 6, fall in water and reach stone 8 respectively. Hence the list is updated accordingly.
- We want you to complete the HashMap for the rest of the stones yourself. In case you get stuck somewhere you can watch the solution video.
- Dear coder, at last your complete HashMap should look like Figure 10.
Here we see that on jumping 5 units from 12th stone it is possible to reach the 17th stone. Hence "true" is returned.
- Reader, we now want you to solve this problem yourself for another input array [0,1,2,,3,4,8,9,11] and tally your answer with the solution video.
import java.io.*;
import java.util.*;
public class Main {
public static boolean solution(int[] stones) {
HashMap< Integer,HashSet< Integer>> map=new HashMap< >();
for(int i=0;i< stones.length;i++){
map.put(stones[i],new HashSet< >());
}
map.get(stones[0]).add(1);
for(int i=0;i< stones.length;i++){
int currStone=stones[i];
HashSet< Integer> jumps=map.get(currStone);
for(int jump:jumps){
int pos=currStone+jump;
if(pos==stones[stones.length-1]){
return true;
}
if(map.containsKey(pos)==true){
if(jump-1>0){
map.get(pos).add(jump-1);
}
map.get(pos).add(jump);
map.get(pos).add(jump+1);
}
}
}
return false;
}
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();
}
System.out.println(solution(arr));
}
}
java;
true";
Analysis
Time Complexity:
O(n2)
The complexity is quadratic because of the use of nested loop.
Space Complexity:
O(n)
The space complexity is of order n where n= number of entries in the HashMap.
Reader, we hope you were able to clearly understand the above discussion. If you have any gaps in your understanding, we suggest you come back to this problem tomorrow.
We'll see you in the next question, goodbye.
