Fewest Hops to Reach the Last Lily Pad
Implement fewestHops
A frog stands on the first of a row of lily pads, and each pad shows the longest hop it can make forward from there. The last pad is guaranteed to be reachable. Find the fewest hops the frog needs to get from the first pad to the last.
A table of the fewest hops to every pad works, but it re-examines earlier pads again and again. Greedy windows do better: the pads reachable with k hops form a block, and the scan only needs to note how far that block can be extended by one more hop.
Example 1:
Input: hops = [3,1,2,1,2,1,1,4]
Output: 4
Example 2:
Input: hops = [1,1,1,1]
Output: 3
Example 3:
Input: hops = [0]
Output: 0
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ hops.length ≤ 15 and 0 ≤ hops[i] ≤ 8; hops[i] is the longest hop the frog can make from pad i - ●
The frog starts on pad 0. From pad i it may hop forward to any pad from i + 1 up to i + hops[i] - ●
The last pad is always reachable - ●
Return the fewest hops needed to reach the last pad (0 if there is only one pad)
hops =
[3, 1, 2, 1, 2, 1, 1, 4]