Why it works
- Every index up to reach can be landed on: a jump to reach can be cut short anywhere. So it is enough to keep one number, not a set of cells.
- A cell with 0 is a dead end only if nothing jumps past it. Taking the farthest reach of all the cells seen so far keeps you off it whenever you can be.
- If i is ever beyond reach, nothing before i jumps that far and nothing after i is reachable at all, so the answer is false. Once reach covers the last index, the answer is true and the rest of the array does not matter.
Complexity
Time O(n): one pass, and it may stop early. Memory O(1): only reach and i.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗