Each element is the maximum jump length from that index. Starting at index 0, return whether you can reach the last index.
Before you code
You don't need to choose jumps. Reachable indexes always form a prefix, so one number, the farthest reach, describes them all.
Hints
- Walk left to right with
far. - If
i > far, return false. - Update
far = max(far, i + nums[i]). Follow-up (Jump game II): count the minimum jumps by expanding reach level by level, like BFS.
Production & complexity notes
When solving Jump game on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in When greedy works to reinforce the underlying pattern.
What it practices
A greedy summary of all choices, from When greedy works.