- 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.