Greedy
01 / The shared mechanism
At every step, take the locally optimal commit — and prove that the commit is never undone later. No backtracking, no DP table: either an exchange argument says swapping any greedy choice cannot improve the answer, or a stays-ahead argument shows greedy keeps a lead at every prefix. Three classic sub-patterns turn that idea into algorithms: sort-and-take on intervals, scan-and-reach on arrays, and a single-pass "reset on failure" on cumulative inputs.
01 / The one-sentence essence
Walk left to right and only ever track the farthest index reachable so far. You don't need to enumerate jumps — if the scan ever passes that frontier the end is unreachable; otherwise it's reached the moment the frontier covers the last index.
Problemcan you reach the last index?nums[2, 3, 1, 1, 4]
Input has 5 cells. We'll scan left to right and keep a single farthest = max index reachable so far.
step
0 / 3
i
—
farthest
0
0 / 3
02 / The pattern signature
# scan once, keep the running max reachfarthest ← 0for i in 0..n−1:if i > farthest: return False # scan outran the frontierfarthest ← max(farthest, i + nums[i])if farthest ≥ n − 1: return Truereturn True# one int of state — no DP, no recursion
03 / When to recognize this pattern
"can you reach the last index"
The textbook trigger (LC 55). The values describe max jump lengths, not exact ones, so feasibility collapses to a one-pass reach check — any prefix that reaches index i can reach anything ≤ i + nums[i].
"minimum number of jumps"
LC 45. Same array, different question — feasibility is given, you optimize the count. Still greedy, but the bookkeeping changes: track the current frontier and the next frontier, and when
i crosses the current you commit a jump and swap in the next. Same O(N), different invariant."can you reach any value from this start"
LC 1306 (Jump Game III). The graph is no longer monotone — from index i you can hop to either
i + arr[i] or i − arr[i]. The farthest-reach trick doesn't apply; degrade to BFS / DFS with a visited set."minimum taps / intervals to cover [0,n]"
LC 1326. Each tap at
i covers [i − r, i + r] — exactly the same shape as "each index reaches i + nums[i]". Rewrite each tap as a reach value and the problem becomes LC 45.04 / Common pitfalls
i.
Confusing reach-checking (LC 55) with min-jumps (LC 45).
Both look like "jump game" but the greedies differ. LC 55 keeps a single
farthest and asks did we ever fall behind it? LC 45 keeps two frontiers — the current one (committed) and the next one (best reachable from inside the current). Don't copy the LC 55 loop and try to count jumps with it.ii.
Reading
nums[i] as "exact jump" instead of "max jump".The value at i is an upper bound — you may land anywhere in
[i+1, i+nums[i]]. That's exactly why the greedy works: from any reachable i, every smaller hop is also free, so the running max suffices and you never need to explore a tree of choices.iii.
Reaching for DP first.
DP works (
can[i] = ∃ j<i, can[j] ∧ j+nums[j] ≥ i) — but it's O(N²) time and O(N) space, where greedy is O(N) and O(1). On any input that fits in memory the DP also does the same checks just less efficiently. If you see "each step is bounded by the value here", default to the scan.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.
— / When to use which
interval scheduling
Use when the input is a list of intervals and the question is "how many non-overlapping picks?" Sort by end, then take each interval whose start clears the last taken end. The exchange argument proves earliest-end is always safe.
sort by end · LC 435 · LC 452
jump game
Use when each element bounds how far you can move from it. Sweep left to right, tracking the farthest index reachable so far; if the sweep ever passes that frontier, the end is unreachable.
track farthest · LC 55 · LC 45
gas station
Use when a cumulative quantity must stay non-negative through a circular or linear walk. Reset the start the moment the running total dips below zero — any failing segment cannot be a valid starting prefix.
reset on failure · LC 134 · LC 53