Reachability: Jump Game & Gas Station

Reachability problems ask whether you can get from the start to the end, or in how few steps, when each position lets you move some distance forward. A DP over "can you reach index i" works but is $O(n^2)$ . The greedy keeps one number, the furthest point reachable so far, and updates it in a single pass.

The idea#

Every index up to the current furthest reach is reachable, because you can always stop short. So you never need to remember which indices are reachable, only how far the reachable prefix goes.

Can you reach the end? Walk left to right. If you're standing past the furthest reach, you're stuck. Otherwise extend the reach with i + nums[i].
Fewest jumps? Think of BFS levels. All indices reachable with j jumps form one contiguous block. When you finish scanning a block, the furthest reach from inside it is the end of the next block, and you've used one more jump.

How to spot it#

These signals in a question point to a reach-based greedy.

"Each element is the maximum jump length", "can you reach the last index", "minimum number of jumps".
Covering a range with intervals or clips ("cover [0, time] with the fewest clips"): the same as jumps, where each start point offers a reach.
A circular route with gains and costs ("gas and cost at each station").

Template#

The template uses the BFS-level view from above, so it answers the fewest-jumps question. level_end is the last index reachable with the jumps used so far, and reach is the furthest index seen from inside that level.

jumps = 0
level_end = 0
reach = 0
for i from 0 to the second-last index:     # no jump from the last one
    if i > reach: stuck, the end is unreachable
    reach = max(reach, i + jump length at i)
    if i == level_end:                     # level finished
        jumps += 1                         # one more jump
        level_end = reach
return jumps

For a yes or no question, drop the levels and keep only the reach check. Each index is visited once, so the scan is $O(n)$ . The table shows how the levels form on two inputs.

`nums`	levels by index	jumps
`[2, 3, 1, 1, 4]`	`{0}`, `{1, 2}`, `{3, 4}`	2
`[2, 3, 0, 1, 4]`	`{0}`, `{1, 2}`, `{3, 4}`	2

Pitfalls#

These mistakes cause the most wrong answers. Several come from the problems below, so they make more sense once you try them.

Looping to the last index when counting jumps. Jumping from the end adds one too many.
Treating a restart rule as an approximation (as in Gas Station). When a greedy skips candidates, prove that none of them could work. A good argument shows each skipped one is no better off than the current one.
Forgetting the global feasibility check. Some problems, such as Gas Station, have no valid answer at all. Check that first, or you return a wrong one.
Missing a gap in coverage. If the next reach doesn't pass the current end, the range can't be covered.
Caching a recursion with shared state. A @cache key that leaves out a shared used list gives wrong answers. Video Stitching invites this mistake.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Jump Game

Keep only the furthest reach. Return False as soon as i passes reach.

Hint: Jump Game II

Count BFS levels. Loop to the second-last index only, and add a jump each time i reaches the end of the current level.

Hint: Video Stitching

Each clip [start, end] lets you jump from any covered point at or after start to end. For every start position, keep the largest end; the problem becomes Jump Game II over time. If the next reach doesn't pass the current end, return -1. A recursion over unused clips with a shared used[] list under @cache is unsound, because the cache key doesn't include used.

Hint: Gas Station

If total gas is less than total cost, no start works; otherwise exactly one does. Walk with a running tank. When it goes negative at station i, no station from the current start up to i can work, since each would reach i with no more fuel than the current start. Restart from i + 1 with an empty tank.

Hint: Jump Game VII

From i you can jump to any '0' in [i + minJump, i + maxJump]. Instead of checking every jump, keep a sliding-window count of reachable indices that can jump to i. Add the index entering the window and remove the one leaving, for $O(n)$ .

Key takeaways#

Reachable indices form a prefix, so one number (the furthest reach) describes them.
Fewest jumps = number of BFS levels, each a contiguous block.
Interval covering is Jump Game in disguise.
In Gas Station, a failure at i rules out every start up to i.

Core idea#

Reachable indices form a prefix, so one number describes them: the furthest reach so far. Update it in a single pass instead of an $O(n^2)$ DP.

Key points#

Can you reach the end? If i passes reach, you are stuck. Otherwise extend reach with i + nums[i].
Fewest jumps: indices reachable with j jumps form one contiguous block, like a BFS level.
When the scan reaches the end of a level, add one jump. The new level ends at the furthest reach.
Video Stitching: keep the largest end for each start, then solve Jump Game II over time.
Gas Station: if total gas is less than total cost, no start works. Otherwise exactly one start works.
Gas Station: when the tank goes negative at i, restart from i + 1 with an empty tank. No start up to i can work.
Jump Game VII: count reachable indices in a sliding window for $O(n)$ .

Template#

jumps = level_end = reach = 0
for i from 0 to the second-last index:     # no jump from the last one
    if i > reach: stuck
    reach = max(reach, i + jump length at i)
    if i == level_end:                     # level done: jump once more
        jumps += 1
        level_end = reach
return jumps

Pitfalls#

Looping to the last index in Jump Game II. That adds one jump too many.
Treating the Gas Station restart as an approximation. It is proven.
Forgetting the total-gas check.
Video Stitching: missing a gap where the next reach does not pass the current end.

Say it in an interview#

"Every index up to the furthest reach is reachable, so one number is enough."
"Fewest jumps is the number of BFS levels, and each level is a contiguous block."