Can the Frog Reach the Last Lily Pad?
Implement canReachLastPad
A frog stands on the first of a row of lily pads. Each pad has a number: the longest hop the frog can make forward from that pad. From pad i it may hop to any pad from i + 1 up to i + hops[i]. Decide whether the frog can reach the last pad.
Working out, pad by pad, which pads are reachable by looking back at every earlier pad is quadratic. A simple greedy insight does it in one pass: the reachable pads always form a solid stretch starting at pad 0, so it is enough to remember how far that stretch extends.
Example 1:
Input: hops = [2,2,0,0,3,1]
Output: false
Example 2:
Input: hops = [1,1,1,1]
Output: true
Example 3:
Input: hops = [0]
Output: true
+ 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] — any distance in that range, not only the maximum - ●
A pad with hops[i] = 0 lets the frog go nowhere. Return true if the frog can reach the last pad, otherwise false
hops =
[2, 2, 0, 0, 3, 1]