Jump Game
You start at the first index of an array where each value is the maximum jump length from that position. Determine whether you can reach the last index.
- 1 ≤ n ≤ 10^4
- 0 ≤ nums[i] ≤ 10^5
- Only the farthest reachable index matters
- Reachable set is always a prefix of the array
- One forward pass updating a single maximum
When a locally best choice (earliest finish time, largest ratio, farthest reach) can be proved never to hurt the global optimum, you can commit to it without exploring alternatives and get O(n log n) from sorting. The proof usually comes via an exchange argument; if you cannot sketch one, suspect DP instead.
Maintain far, the farthest index reachable so far, starting at 0. Scan left to right; if the current index exceeds far, it is unreachable and so is everything after — return false. Otherwise update far = max(far, i + nums[i]). If the scan finishes (or far reaches the last index), return true. The set of reachable positions is contiguous, which is why one number captures it.
- A DP marking reachable indices costs O(n · maxJump). Scanning backward with a "last good index" is an equivalent greedy.