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
The tank can't be negative anywhere in the loop. If the running tank dips below zero at any prefix, every starting index in that prefix is dead — reset start past the failure.
Problemfind a start that completes the loopgas[1, 2, 3, 4, 5]cost[3, 4, 5, 1, 2]
Two parallel arrays of length 5. At each station, diff = gas − cost goes into the tank; the tank can never dip below zero.
step
0 / 9
i
—
tank
0
start
0
0 / 9
02 / The pattern signature
# one pass, two accumulatorstotal ← 0; tank ← 0; start ← 0for i in 0..n−1:diff ← gas[i] − cost[i]total += difftank += diffif tank < 0:start ← i + 1 # this whole segment is deadtank ← 0return start if total >= 0 else −1
03 / When to recognize this pattern
"circular route, complete the loop"
The classic LC 134 phrasing. A ring of stations, a tank that picks up
gas[i] and burns cost[i], and you need a starting index that carries you all the way around. Linearize the ring — if total ≥ 0, a valid start exists and the reset loop finds it."running sum must stay non-negative"
Any time the question is "does this cumulative quantity ever go below zero?" — balance, fuel, energy, water level. The same one-pass reset trick applies: a failing prefix can never be a valid starting prefix.
"maximum subarray (Kadane)"
LC 53 is the same shape with the sign flipped: reset the running sum to zero when it drops below zero, because any prefix that drags the running sum negative is dead weight against future elements. Gas Station resets start; Kadane resets sum. Same proof.
"longest valid prefix / wraparound"
When the input is circular but the answer is a contiguous arc, and the proof rules out most candidates in a single sweep. Pair the reset trick with a total-feasibility check at the end.
04 / Common pitfalls
i.
Not checking
total at the end.Without the final
total >= 0 check you may return a start when the loop is actually impossible — every reset moved start forward, so it'll point somewhere even on degenerate input. The totals tell you whether any start works; the reset loop only finds which one.ii.
Off-by-one in the reset.
When
tank < 0 after processing i, the new start is i + 1 — not i. Index i is dead too: the prefix [start..i] dipped negative, so no station in it can be a valid origin. Off by one and you re-pick a dead start; sometimes the answer is still correct by luck, but on adversarial inputs it isn't.iii.
Misunderstanding the proof — trying every start in O(n²).
Students often fall back to "try each index and simulate the loop". The key insight is that a failing prefix kills every start inside it: if
start..i goes negative, then j..i for any j ∈ [start, i] is also negative (it's a suffix of a sum that already dipped below zero with extra positive runway in front). That's the whole pattern — one pass is enough.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. LC 53 is the same reset trick on a single signed array — worth solving first if Kadane isn't already in your hands.
— / 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