Jump Game
Jump Game is a medium Greedy problem from the Blind 75. The key pattern is greedy reach, and a good solution runs in O(n) time.
Problem
Each value is the maximum forward jump length; determine whether the final index is reachable.
Examples
Example 1
Input
[3,2,1,0,4]Output
falseExample 2
Input
[3,1,0,2,0,1]Output
trueExample 3
Input
[0]Output
trueApproach
Track the farthest index reachable so far. If you ever stand beyond it you are stuck; if it reaches the end you can finish.
| Pattern | Greedy reach |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
A 0 only blocks you when the reach cannot get past it.