Loading page…
Practice problem · easy
A maps app plans a trip along one bus line. The stops are numbered 0 to n - 1, and the trip starts at stop 0. At a stop, a rider may switch to an express shuttle that goes forward by up to a fixed number of stops.
The rider can get off at any stop on the way. Some stops have no shuttle.
Your team lead asks: "Can a rider get from the first stop to the last stop?"
Write can_reach_the_last_stop(hops).
hops[i] is the most stops ahead that the shuttle at stop i can go. From stop i a rider can reach any stop from i + 1 to i + hops[i]. A value of 0 means no shuttle there.true if a rider starting at stop 0 can reach stop n - 1, and false if not.true.Input: hops = [2, 0, 0, 1, 5]
Output: falseKeep farthest, the farthest stop you can reach so far. At each stop, if the stop is beyond farthest, you are stuck. Otherwise farthest becomes the larger of itself and i + hops[i].
| Stop | hops | Reachable? | farthest after |
|---|---|---|---|
| start | 0 | ||
| 0 | 2 | yes: 0 is at most 0 | 2 |
| 1 | 0 | yes: 1 is at most 2 | 2 |
| 2 | 0 | yes: 2 is at most 2 | 2 |
| 3 | 1 | no: 3 is beyond 2 | stuck |
Stop 3 cannot be reached, so stop 4 cannot be either. The answer is false.
Input: hops = [2, 3, 1, 1, 4]
Output: trueStop 0 reaches stop 2. Stop 1 is on the way and its shuttle goes 3 stops, so stop 4 is in reach.
Input: hops = [0]
Output: trueThere is only one stop, so the rider is already at the last stop.
1 ≤ len(hops) ≤ 100,0000 ≤ hops[i] ≤ 100,000There can be 100,000 stops, and each stop can offer many different hop lengths. Trying every route can take an exponential number of steps, which never finishes. One pass over the stops costs 100,000 steps.
can_reach_the_last_stop · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.