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

FROG JUMP

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

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 0^{th} stone, will it be able to reach the 17^{th} stone.

Let's figure out how the frog must jump.

- When the frog is at 0
^{th}stone then according to the question it can jump by 1 unit only and hence reaches the 1^{st}stone. - On reaching the 1
^{st}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 3^{rd}stone. - Since the last jump was of 2 units, therefore k=2. On reaching 3
^{rd}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 5^{th}stone and step on the 6^{th}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 0
^{th}stone, a jump of 1 unit is applied. Hence k=1 and we can now find the possible jumps for 1^{st}stone i.e. 0, 1 and 2. We do not include a jump of 0 units in the HashMap. - Now for the 1
^{st}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 3^{rd}stone. Hence the possible jumps for 3^{rd}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 12
^{th}stone it is possible to reach the 17^{th}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(n^{2})

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.