Jump Game
The problem
Each nonnegative array value is the maximum jump length allowed from that index. Starting at index 0, determine whether you can reach the final index of a nonempty array.
Example
[2, 0, 2, 0, 1] → true; [1, 0, 2] → false
Need a hint?
Track the farthest reachable index rather than committing to a particular jump.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Scan while the current index is within the reachable range. Extend farthest with max(farthest, index + jumpLength). Return true once it reaches the last index. If the next index lies beyond farthest, an unavoidable gap makes the answer false.
Complexity
O(n) time and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.