Jump Game (LeetCode #55)

Jump Game (LeetCode #55) asks whether you can reach the last index of an array where each value nums[i] is the maximum distance you may jump forward from i. The greedy solution scans the array once, maintaining a single number — reach, the farthest index provably reachable — and decides the whole problem in O(n) time and O(1) space.

Your first instinct is probably to search: try a jump, recurse, backtrack. Without memoization that search can repeat paths exponentially; memoized over positions it still costs O(n²) in the worst case. Either way it buys you nothing, because this problem has a property that collapses the entire search space into one integer. From any reachable cell i you may jump any distance from 1 to nums[i] — not just the maximum — so the set of reachable indices is never scattered. It is one solid block starting at 0. A solid block is fully described by its right edge. That right edge is reach, and the algorithm is nothing but the bookkeeping of that edge.

How Jump Game Works

The scan visits every index left to right and does two things, in an order that matters more than it looks.

First, the guard: if i > reach, return False. The scan has walked past the frontier — index i is unreachable, and so is everything after it. There is no waiting for a rescue. Every cell that could launch you forward lives at some index ≤ reach, all of them have already been folded into reach, and their best combined effort is exactly reach. If that isn't enough to touch i, no value sitting beyond the gap will ever get a chance to matter. A trampoline you can't reach is furniture.

Second, the update: reach = max(reach, i + nums[i]). Cell i offers landings on every index up to i + nums[i]; if that beats the current frontier, the frontier moves. Note what the algorithm does not track: which cells you'd actually jump through, where you'd land, any path at all. It doesn't need to. Because jump lengths are "up to", any index inside the frontier is reachable, so the block stays solid and one number keeps carrying the entire state. That is also the test for reusing this trick elsewhere: it works exactly when the reachable set is guaranteed contiguous. Make the jumps exact distances instead of "up to", or forbid certain cells, and the set can grow holes — no single right edge describes it anymore, and you are back to BFS or DP.

The guard runs before the update, and the order is load-bearing. Flip the two and reach gets updated from an index you never could have stood on — after the update reach ≥ i always holds, so the guard can never fire and every input returns True. An unreachable cell would launder itself into a launch pad.

If the loop finishes, every index — the last one included — stayed inside the frontier. Return True.

Jump Game Step by Step

The default input is nums = [2, 3, 1, 0, 4], and it exists to prove that a zero is not a death sentence:

1. i = 0. The guard passes (0 ≤ 0). Cell 0 offers jumps to indices 1 and 2, so reach = max(0, 0 + 2) = 2.
2. i = 1. Inside the frontier (1 ≤ 2). The update gives reach = max(2, 1 + 3) = 4 — the frontier now covers the last index. The verdict is already sealed; the scan just doesn't know it yet.
3. i = 2. Guard passes. 2 + 1 = 3 lands under the frontier of 4. No gain, no drama.
4. i = 3. Here sits the zero. It offers nothing: max(4, 3 + 0) = 4. But the guard only asks whether 3 ≤ 4, and it is. The zero is survived — the frontier had already sailed past it back at step 2.
5. i = 4. Guard passes (4 ≤ 4), and this is the last index. The update even pushes reach to 8, past the end of the array — the frontier doesn't care where the array stops. The loop ends: True.

Now swap the first two values: nums = [3, 2, 1, 0, 4] (LeetCode's own example 2, and the "Every path funnels" preset). Same five numbers, opposite verdict. Cell 0 reaches index 3; cells 1 and 2 offer 1 + 2 = 3 and 2 + 1 = 3. Every single arc lands exactly on the zero. The frontier stalls at 3, the zero adds nothing, and at i = 4 the guard finally fires: 4 > 3, return False. The tempting 4 in the last cell never enters the story — it lives on the far side of the gap.

In the animation, the green rail under the cells is reach made visible: each orange arc is one cell's offer, and the rail tip only moves when an arc outreaches it. The first time the frontier grows, the player pauses to prove the point: it fans out every allowed landing, shows the new interval as its own segment next to the rail, then folds the two into one longer rail — the solid-block argument performed on screen. On the failure preset you can watch three arcs pile onto the same cell and the rail freeze — the gap then draws itself as the dashed red rail that should have been there.

Time and Space Complexity

Each index is visited once and does constant work. The common micro-optimization — return True early once reach ≥ n − 1 — changes none of the bounds; the animated version deliberately scans on, because watching the zero get survived after the verdict is sealed is the point of the default input.

Edge Cases

• Single element, even [0]: you are already standing on the last index. The loop runs once and returns True without any jump.
• Leading zero with more array after it, like [0, 3]: the frontier never leaves index 0, and the guard fires immediately at i = 1.
• Overshoot: reach can exceed n − 1 (the default ends at reach = 8 with n = 5). Nothing special is needed — i never exceeds n − 1, so the guard comparison stays honest.
• Where the gap opens: always at exactly reach + 1. The guard cannot fire later than that, because every index up to reach passes it by definition.

Common Mistakes

• Zero panic — returning False on sight of nums[i] == 0. A zero is only fatal when the frontier stalls exactly on it; the default input has a zero and succeeds. Reachability belongs to the frontier, not to any single cell.
• Updating before guarding — computing reach = max(reach, i + nums[i]) and then checking i > reach. The check can never fail after the update, so the function degenerates into return True.
• Simulating actual jumps — always jumping the full nums[i], or running BFS over landing positions. The "up to" in the jump rule is the entire problem: on [2, 3, 0, 1, 4] the maximal-jump simulation leaps from index 0 straight onto the zero and dies there, while the real answer is True because landing one short, on the 3, was always allowed. BFS gets the right answer but pays O(n²) for information one integer already carries.
• Reading meaning into the last value — nums[n − 1] never matters. You jump to the last index, not from it, and a large value beyond the gap is unreachable furniture.