Loading...
Loading...
Loading...
On a college trek, Isha crosses a stream on a line of n stones, numbered 0 to n - 1. Stone i has a number a[i]: from stone i she can jump forward 1, 2, … up to a[i] stones. A stone with 0 is a dead end.
She starts on stone 0. Print the fewest jumps she needs to reach stone n - 1. If she can never reach it, print -1.
-1.Example 1
Input
5 2 3 1 1 4
Output
2
Jump 1 stone to stone 1, then 3 stones to stone 4. That is 2 jumps.
Example 2
Input
5 3 2 1 0 4
Output
-1
Every path lands on stone 3, which has 0, so stone 4 cannot be reached.
Try the problem first. Open one hint at a time.
Let jumps[i] be the fewest jumps to land on stone i. jumps[0] = 0, and every other stone starts as "not reached".
Go through the stones from left to right. From a reached stone i, every stone i + 1 to i + a[i] can be reached in jumps[i] + 1.
Keep the smaller value at each stone. Skip stones that were never reached, and print -1 if the last stone stays unreached.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor