Greedy Reachability and Jumps

Jump Game looks like dynamic programming. “Can I reach the end?” invites a dp[i] = can I reach index i? table, and that works — in $O(n^2)$.

The greedy insight collapses it to $O(n)$ and one variable:

You do not need to know which path reaches an index. You only need to know how far you can reach at all.

Reachability is a single number, not a set. Because it only ever grows, one forward pass maintaining max_reach answers the question completely.

What you’ll learn

• The max_reach scan, and why “if i > reach, fail” is a complete test.
• The level-BFS view of minimum jumps — why LC 45 counts jumps without ever choosing one.
• The two-part structure of Gas Station: a feasibility check plus a restart rule.
• Why these greedies are provably optimal, and where the same shape fails.
• Three real LeetCode problems solved in the browser: 55, 45, 134.

The cue

You are looking at a reachability greedy when…

• “Can you reach the last index / the end / the target?” — 55.
• “Minimum number of jumps / steps / taps / clips” to cover a span — 45, 1024, 1326.
• You are covering a range rather than selecting a subset. (Selecting is Greedy Interval Scheduling.)
• A circular array where you need a valid starting point — 134.
• The DP is obvious and $O(n^2)$, and the constraints say $n \le 10^5$ — that gap is the hint.

Visual intuition

The whole algorithm is one number — the frontier, the furthest index reachable so far. Watch the band: it only ever widens, and the answer is whether it swallows the last index.

arrayYou never choose a jump — you only widen the reachable prefixLC 55 · O(n) time, O(1) space

reachable · farthest = 0

2031121344

i

1def can_jump(nums):2    farthest = 03    for i, n in enumerate(nums):4        if i > farthest:5            return False        # the frontier never reached here6        farthest = max(farthest, i + n)7    return True

farthest0

seedThe frontier starts at index 0 — before taking any jump, only the first cell is reachable. The greedy never decides *which* jump to take: it only ever widens this band, and the answer is whether the band reaches the last index.

Play‹›1/4⟲

Note what is NOT happening: no branching over jump lengths, no DP table, no recursion. Each cell contributes exactly one candidate, i + nums[i], and the frontier keeps the max. From index 1 the frontier reaches the end, so the scan stops early.

And the failing shape — a 0 that the frontier cannot step over:

arrayThe only failure mode: arriving at an index beyond the frontierLC 55 · returns False

reachable · farthest = 0

3021120344

i

1def can_jump(nums):2    farthest = 03    for i, n in enumerate(nums):4        if i > farthest:5            return False        # the frontier never reached here6        farthest = max(farthest, i + n)7    return True

farthest0

seedThe frontier starts at index 0 — before taking any jump, only the first cell is reachable. The greedy never decides *which* jump to take: it only ever widens this band, and the answer is whether the band reaches the last index.

Play‹›1/6⟲

Indices 1, 2 and 3 each reach exactly 3 and never push the frontier past it. At index 4 the loop finds i > farthest, which proves nothing can reach index 4 -- and therefore nothing beyond it either. One comparison decides the whole problem.

Pattern 1 — can I get there at all?

Sweep left to right maintaining the furthest index reachable so far. If the loop ever arrives at an index beyond that reach, there is a gap nothing can cross.

can_jump.py

def can_jump(nums):
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False              # a gap: nothing reaches index i
        reach = max(reach, i + jump)
    return True
 
 
print(can_jump([2, 3, 1, 1, 4]))      # True
print(can_jump([3, 2, 1, 0, 4]))      # False -- stuck at the 0

$O(n)$ time, $O(1)$ space.

Why one number is enough

The set of reachable indices from the start is always a contiguous prefix [0, reach]. It cannot have holes: if you can reach index j, you can reach every index below j, because any jump of length k can be under-shot — you may always stop earlier by taking a smaller step from the same launching point.

Since the reachable set is an interval starting at 0, it is fully described by its right endpoint. That is why reach suffices where a dp array seemed necessary, and it is the sentence to say out loud when asked why the greedy is valid.

Pattern 2 — minimum jumps, as implicit BFS

For the number of jumps, think in levels, exactly like BFS: level 0 is index 0; level 1 is everything reachable in one jump; level 2 everything reachable in two. The answer is the level containing the last index.

You never decide which jump to take. You only notice when the current level is exhausted and a new one must begin.

min_jumps.py

def min_jumps(nums):
    jumps = 0
    current_end = 0        # right edge of the current BFS level
    farthest = 0           # right edge of the NEXT level
 
    for i in range(len(nums) - 1):        # note: stop BEFORE the last index
        farthest = max(farthest, i + nums[i])
        if i == current_end:              # current level exhausted
            jumps += 1                    # commit to one more jump
            current_end = farthest        # descend into the next level
    return jumps
 
 
print(min_jumps([2, 3, 1, 1, 4]))   # 2  -> 0 -> 1 -> 4

range(len(nums) - 1), not range(len(nums))

The loop must stop before the final index. If you include it and the last index happens to coincide with current_end, you increment jumps once more for a jump you never need to take — because you have already arrived.

On [0] (a single element, answer 0) the off-by-one version returns 1. That test case is in the exercise below for exactly this reason.

Pattern 3 — feasibility plus restart (Gas Station)

Gas Station has two independent halves, and separating them is what makes it easy:

1. Is any circuit possible? Only if sum(gas) >= sum(cost). Otherwise return -1 immediately — no starting point can work.
2. Given that one exists, which index? Sweep once with a running tank. Whenever the tank goes negative at index i, no start in [current_start, i] can work, so jump the candidate start to i + 1 and reset the tank.

gas_station.py

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1                   # globally impossible
 
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                # cannot get from `start` past i
            start = i + 1           # so try starting after i
            tank = 0
    return start
 
 
print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3

Why the single pass finds it, and why it is unique

Why skipping is safe. Suppose starting at s the tank first goes negative at i. Then for any t between s and i, the run from t to i is a suffix of the run from s to i. Every prefix from s was non-negative, so the segment s..t-1 contributed a non-negative amount — meaning starting at t arrives at i with no more fuel than starting at s did. It fails too. So the whole range [s, i] can be discarded at once, which is what makes one pass enough.

Why the survivor works. If the global total is non-negative, exactly one candidate survives to the end, and the same argument shows the wrap-around portion is covered by the surplus accumulated before it. The problem also guarantees the answer is unique when it exists.

Dry run

LC 55 — can I reach the end? nums = [2, 3, 1, 1, 4]:

i	nums[i]	i + nums[i]	frontier after	note
0	2	2	2	—
1	3	4	4	frontier now covers index 4, the last one → True, stop early

Two iterations for a five-element array. Contrast [3, 2, 1, 0, 4]:

i	nums[i]	i + nums[i]	frontier after
0	3	3	3
1	2	3	3 — no improvement
2	1	3	3
3	0	3	3
4	—	—	i > farthest → False

• The zero is not what fails — the frontier is. Indices 1, 2 and 3 all reach exactly 3, so the frontier stalls. Index 4 is then beyond it, and because the frontier is a maximum over everything seen, nothing later can rescue it either. That is why one comparison settles the whole problem.
• You never decide how far to jump. Each index contributes one candidate and the max wins. This is why the greedy is safe: there is no choice to get wrong.

LC 45 — minimum jumps, same array. Two frontiers now: current_end (the right edge of the level you are on) and farthest (the right edge of the next level). The loop stops at n - 1:

i	farthest after	current_end	at boundary?	jumps after
0	2	0	yes → take a jump, current_end = 2	1
1	4	2	no	1
2	4	2	yes → take a jump, current_end = 4	2
3	4	4	no	2

Answer 2 — jump from 0 to 1, then 1 to 4.

• This is BFS with the queue erased. Each “level” is the set of indices reachable in the same number of jumps, and current_end is that level’s right edge. Incrementing jumps when i reaches the boundary is the level transition — the same shape as processing a BFS layer, with no queue because the levels are contiguous ranges.
• The loop must stop at n - 1, not n. Arriving at the last index means you are done; including it would count one extra jump for landing where you already are. That off-by-one is the standard LC 45 bug, and [0] → 0 is the test that catches it.
• Every index is visited once. $O(n)$ time, two integers of state — no queue, no visited set, no DP array.

Complexity

Problem	Greedy	Obvious DP / brute force
55 Jump Game	$O(n)$ / $O(1)$	$O(n^2)$ / $O(n)$
45 Jump Game II	$O(n)$ / $O(1)$	$O(n^2)$ / $O(n)$
134 Gas Station	$O(n)$ / $O(1)$	$O(n^2)$ — try every start

The variant map

Variant	What you track	Canonical problem
Reachable at all	One max_reach	55 Jump Game
Minimum jumps	current_end + farthest (BFS levels)	45 Jump Game II
Cover a range with intervals	Same two variables, over clips	1024 Video Stitching · 1326
Circular, find the start	Feasibility check + restart index	134 Gas Station
Arbitrary jumps, may go backwards	Greedy fails — use real BFS	1306 Jump Game III

Backward moves kill the greedy

LC 1306 lets you jump i + arr[i] or i - arr[i]. The reachable set is no longer a contiguous prefix, so a single reach number cannot describe it, and the whole argument collapses.

That problem needs an actual BFS or DFS with a visited set. Recognising why the greedy stops applying — monotonicity of the reachable set is gone — matters more than knowing that it does.

Practice — real LeetCode problems

LC 55 — Jump Game · Medium

Problem. You start at index 0 of nums, where nums[i] is the maximum jump length from index i. Return True if you can reach the last index.

Constraints. 1 <= len(nums) <= 10^4, 0 <= nums[i] <= 10^5.

Examples. [2,3,1,1,4] gives True · [3,2,1,0,4] gives False (the 0 at index 3 is a wall) · [0] gives True (already there)

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-uups

Maintain reach, the furthest index attainable using any sequence of jumps from indices already visited. Standing at index i with i <= reach means i is genuinely attainable, so its jump extends the frontier. If the scan reaches an i with i > reach, every index from there on is unreachable and the answer is False.

Time $O(n)$. Space $O(1)$.

The correctness rests on reachability being a contiguous prefix — see the note above. That is the answer to “why doesn’t this need DP?”.

Test-case notes: [0] gives True because you begin at the last index — no jumping required. [2,0,0] gives True because the first jump of 2 clears both zeros. [1,0,1,0] gives False: from index 0 you reach only index 1, whose value is 0, so index 2 is unreachable.

A backward variant exists and is worth mentioning: scan right to left tracking the leftmost index known to reach the end, and check whether index 0 qualifies. Same complexity, and some find the invariant easier to state.

Follow-ups you should expect: “Minimum number of jumps?” — LC 45, below. “What if nums[i] were an exact jump length rather than a maximum?” — the prefix property breaks and it becomes a BFS. “Can you jump backwards?” — LC 1306, also BFS. “Reconstruct the path?” — record the launching index each time reach improves.

LC 45 — Jump Game II · Medium

Problem. Same setup, but you are guaranteed to be able to reach the last index. Return the minimum number of jumps required.

Constraints. 1 <= len(nums) <= 10^4, 0 <= nums[i] <= 1000, and reaching the end is always possible.

Examples. [2,3,1,1,4] gives 2 (index 0 → 1 → 4) · [2,3,0,1,4] gives 2 · [0] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Group indices by the minimum number of jumps needed to reach them. Level 0 is {0}; level 1 is everything reachable from level 0; and so on. The answer is the level of the last index — which is precisely BFS shortest path on an unweighted graph, with the levels being contiguous ranges so no queue is needed.

While scanning within a level, farthest accumulates the union of everything that level can reach. When i hits current_end, the level is finished: increment the jump count and adopt farthest as the new boundary.

Time $O(n)$. Space $O(1)$.

The loop bound is the one real trap. [0] must give 0: you start at the last index. With range(len(nums)), i = 0 == current_end triggers an increment and returns 1. Stopping at len(nums) - 1 means arriving is never charged a jump.

[1,1,1,1] giving 3 is a good sanity check that levels are being counted rather than positions — each jump advances exactly one index.

Follow-ups you should expect: “Prove it is optimal” — it is BFS, and BFS gives shortest paths on unweighted graphs; the greedy is just BFS with the queue replaced by two integers, valid because each level is a contiguous range. “Return the actual jump sequence?” — record the index achieving farthest for each level. “What if reaching the end were not guaranteed?” — detect current_end failing to advance (farthest == current_end before the end) and return -1. “Weighted jump costs?” — no longer BFS; Dijkstra or DP.

LC 134 — Gas Station · Medium

Problem. There are n gas stations in a circle. gas[i] is the fuel available at station i, and cost[i] is the fuel needed to travel from i to i+1. Starting with an empty tank, return the index of the station from which you can complete the circuit, or -1 if none exists. The answer is guaranteed unique.

Constraints. 1 <= len(gas) == len(cost) <= 10^5, 0 <= gas[i], cost[i] <= 10^4.

Examples. gas = [1,2,3,4,5], cost = [3,4,5,1,2] gives 3 · gas = [2,3,4], cost = [3,4,3] gives -1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Splitting the problem is the whole idea:

• Feasibility is global. Total fuel must cover total cost; otherwise no starting point helps. This check also removes any need to handle wrap-around explicitly.
• Location is local. One left-to-right sweep suffices, because a failure at index i eliminates every candidate start up to i at once — see the note above for why.

Time $O(n)$, one pass plus two sums. Space $O(1)$.

The subtlety is that the loop never wraps around, yet the answer is correct for a circular route. That is what the feasibility check buys: given a non-negative global surplus, the single surviving candidate is guaranteed to make it round, so you never have to simulate the wrap.

([3,1,1],[1,2,2]) returning 0 is worth tracing: totals are 5 and 5, so feasible. From index 0 the tank runs +2, +1, 0 and never goes negative, so start stays 0.

Follow-ups you should expect: “Why don’t you need to simulate the wrap-around?” — the most likely question; the feasibility check plus uniqueness guarantee it. “What if multiple valid starts existed?” — this pass returns the first; collecting all of them needs a second pass. “What if you begin with k fuel already?” — add k to the initial tank and the same argument holds. “Do it with a prefix sum?” — yes, and it is elegant: the answer is the index just after the minimum prefix sum of gas[i] - cost[i], which is an equivalent framing worth mentioning.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1024 is LC 45 wearing different clothes

Video Stitching asks for the fewest clips covering [0, time]. Sort clips by start, then run exactly LC 45’s two-variable loop: within everything starting at or before your current coverage edge, track the furthest right end; when you hit the edge, commit to one more clip and jump the edge outward.

Same current_end / farthest pair, same level-counting. And note it is the opposite of Greedy Interval Scheduling — there you sort by end to select non-overlapping intervals; here you sort by start to cover a range. Asking “am I selecting or covering?” picks the right greedy every time.

8 problems

0 easy8 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○45Jump Game IImediumBFS levels without a queue; mind the loop boundNeetCode 150LeetCode Top Interview 150
• ○55Jump GamemediumOne `reach` variable; reachability is a contiguous prefixNeetCode 150Blind 75LeetCode Top Interview 150
• ○122Best Time to Buy and Sell Stock IImediumLeetCode Top Interview 150
• ○134Gas StationmediumGlobal feasibility check + local restart ruleNeetCode 150LeetCode Top Interview 150
• ○678Valid Parenthesis StringmediumNeetCode 150
• ○1024Video StitchingmediumLC 45's greedy over intervals: cover `[0, time]` with fewest clips
• ○1306Jump Game IIImediumBackward jumps allowed -- greedy **fails**, use BFS/DFS
• ○1899Merge Triplets to Form Target TripletmediumNeetCode 150

Interview follow-ups

They ask	What they’re checking	The answer
“Why doesn’t this need DP?”	The key insight	The reachable set is a contiguous prefix [0, reach], so one integer fully describes it
“Prove the minimum-jump greedy is optimal”	Rigour	It is BFS on an unweighted graph; each level is a contiguous range, so two integers replace the queue
“Why is Gas Station one pass?”	Depth	A failure at i eliminates every start up to i, because those runs are suffixes of an already non-negative prefix
“Why no wrap-around simulation?”	Care	The global feasibility check plus the uniqueness guarantee make the surviving candidate valid
“What if you can jump backwards?”	Knowing the boundary	The prefix property dies; use BFS/DFS with visited (LC 1306)
“What if jumps were exact, not ‘up to’?”	Same boundary	Reachability stops being contiguous, so greedy fails
“Reconstruct the path?”	Bookkeeping	Record the launching index whenever farthest improves

Edge-case checklist

• Single element — [0]; LC 55 gives True, LC 45 gives 0. The loop-bound test.
• Leading zero with length > 1 — [0, 1]; unreachable, False.
• A zero you can jump over — [2,0,0] gives True; a zero is only fatal if you must land and stop on it.
• Zero that traps you — [3,2,1,0,4]; the canonical False.
• Very large jump values — i + nums[i] may exceed the last index; harmless with max, but do not index with it.
• All zeros — [0,0,0] is False for LC 55 (length > 1).
• Gas equals cost exactly — feasible with zero slack; ([5],[4]) and ([3,1,1],[1,2,2]) cover the boundary.
• Single station (LC 134) — valid if gas[0] >= cost[0].
• Tank exactly zero mid-route — 0 is not negative, so the trip continues; only < 0 triggers a restart.

Self-check

pch.quizTag Greedy reachability and jumps — self-check

1. In LC 55, why is a greedy safe here when it fails on so many other problems?

   A Because the array is small B Because there is no choice to make — each index contributes exactly one candidate, i + nums[i], and the frontier keeps the maximum. You never decide how far to jump C Because the values are non-negative D It is not safe; it is a heuristic
   pch.quizShowAnswer

   B — Because there is no choice to make — each index contributes exactly one candidate, i + nums[i], and the frontier keeps the maximum. You never decide how far to jump — Greedy fails when a locally good choice forecloses a better one. Here the 'choice' is a max over everything seen so far, so nothing can be foreclosed.

2. On [3, 2, 1, 0, 4] the answer is False. What exactly fails?

   A The 0 at index 3 blocks the path B Index 4 is beyond the frontier: indices 1–3 all reach exactly 3, so `i > farthest` fires — and because the frontier is a maximum over everything seen, nothing later can rescue it C The array length is odd D The frontier decreases
   pch.quizShowAnswer

   B — Index 4 is beyond the frontier: indices 1–3 all reach exactly 3, so `i > farthest` fires — and because the frontier is a maximum over everything seen, nothing later can rescue it — The zero is a symptom, not the test. Framing it as 'the frontier stalled' is what generalises to LC 1306 and the other reachability variants.

3. LC 45 asks for the MINIMUM number of jumps. Why is that still O(n) and not BFS with a queue?

   A Because the graph is a tree B Because it IS a BFS — each level is a contiguous range of indices, so `current_end` (this level's right edge) and `farthest` (the next level's) replace the queue entirely C Because jumps are always 1 D Because the array is sorted
   pch.quizShowAnswer

   B — Because it IS a BFS — each level is a contiguous range of indices, so `current_end` (this level's right edge) and `farthest` (the next level's) replace the queue entirely — Recognising the levels as contiguous ranges is what removes the queue. Incrementing `jumps` when i reaches current_end is precisely the level transition.

4. In LC 45 the loop runs to `n - 1`, not `n`. Why?

   A To avoid an index error B Because arriving AT the last index means you are already done — including it would count one extra jump for landing where you already are C Because the last element is never used D To keep the loop O(n)
   pch.quizShowAnswer

   B — Because arriving AT the last index means you are already done — including it would count one extra jump for landing where you already are — The classic off-by-one in this problem. The single-element case [0] → 0 is the test that catches it, and it is worth writing before submitting.

5. Gas Station (LC 134) uses the same shape. What is the extra idea?

   A Sorting the stations by cost B If the total gas covers the total cost a solution must exist, and whenever the running tank goes negative the start must move past every station tried so far — so one pass finds it C Binary searching the starting index D Trying every start until one works
   pch.quizShowAnswer

   B — If the total gas covers the total cost a solution must exist, and whenever the running tank goes negative the start must move past every station tried so far — so one pass finds it — Two claims, both needed: total ≥ 0 guarantees existence, and the restart rule skips a whole prefix at once instead of retrying each start — turning O(n²) into O(n).

6. Could you solve LC 55 with dynamic programming instead?

   A No, DP does not apply B Yes — dp[i] = 'is i reachable' is correct but O(n²), because each index scans every earlier one; the greedy collapses that entire table into a single running maximum C Yes, and it is faster D Only for arrays without zeros
   pch.quizShowAnswer

   B — Yes — dp[i] = 'is i reachable' is correct but O(n²), because each index scans every earlier one; the greedy collapses that entire table into a single running maximum — Being able to name the DP and then explain what the greedy replaces is a stronger answer than the greedy alone — it shows the O(n) is a deliberate improvement, not a lucky guess.

Recall card

• Cue — “can you reach the end”, “minimum jumps”, “is there a valid starting point”; each position permits a range of moves rather than one.
• Reachability (LC 55) — one variable: farthest = max(farthest, i + nums[i]), and fail the moment i > farthest. $O(n)$ time, $O(1)$ space.
• The frontier only widens — that is why the greedy is safe: there is no choice to make wrong.
• Minimum jumps (LC 45) — two frontiers, current_end and farthest; increment jumps when i reaches current_end. It is BFS with the queue erased, because each level is a contiguous range.
• Loop to n - 1 in LC 45. Arriving at the last index is already done; [0] → 0 is the test.
• Gas Station (LC 134) — total gas ≥ total cost proves a solution exists; reset the start whenever the running tank goes negative.
• Contrast — the DP formulation (dp[i] reachable) is correct and $O(n^2)$; the greedy collapses it to one running maximum.

Recap

• Track how far you can reach, not how you got there. Reachability is a contiguous prefix, so one integer replaces an entire DP array — $O(n)$ and $O(1)$.
• Can I reach the end? Fail the moment the scan stands beyond reach.
• Minimum jumps is BFS by levels with the queue replaced by current_end and farthest. Loop to len(nums) - 1, or a single element wrongly costs a jump.
• Gas Station splits into a global feasibility check (sum(gas) >= sum(cost)) and a local restart rule, which together avoid simulating the wrap-around.
• Covering a range sorts by start and extends furthest; selecting non-overlapping intervals sorts by end. Ask which you are doing.
• The greedy dies when the reachable set stops being contiguous — backward or exact-length jumps mean real BFS.

Next: Sorting with Custom Comparators — the greedy prerequisite, and how to express an ordering that is not just “ascending”.