LC Patterns — Greedy

Greedy has no data-structure boilerplate — the "template" is a discipline:

1. SORT by the key that makes the greedy choice safe   ← 80% of the thinking
2. One pass, maintaining a small invariant (1–3 variables)
3. Per element: commit / skip / extend, per the rule
4. PROOF: one spoken sentence — exchange, staying-ahead, or invariant

Universal pitfalls

1. Wrong sort key. Sorting by start when the proof needs end (interval selection), by absolute value when it needs the difference (two-city). The exchange argument dictates the key — derive it, don't guess. If you can't finish the sentence "sorting by X is safe because swapping any two adjacent items ordered otherwise can't help", the key is wrong.
2. No counterexample search. The classic trap problems (e.g. coin change with arbitrary denominations — LC 322) look greedy and aren't. Spend 30 seconds trying to break your own rule before coding; interviewers plant these.
3. Ties. Equal ends, equal starts, equal counts — decide tie order consciously; several problems hide their hardest cases in ties.
4. Claiming greedy without the proof. Even when correct, an unjustified greedy reads as a lucky guess. One sentence fixes it.
5. Greedy on the wrong quantity. "Maximize items" ≠ "maximize value" — interval count problems sort by end; weighted versions are DP (LC 1235). Check which one you were asked.
6. Off-by-one in invariant updates — updating furthest before vs after the boundary check (jump problems), popping vs peeking order (stack greedy). Trace a 4-element example by hand.

What it is: From n intervals, select the maximum number of mutually non-overlapping ones (equivalently: remove the minimum to make the rest disjoint, or pierce all with the fewest arrows). Sort by end; take every interval that starts after the last taken end.

Intuition: the interval that ends earliest leaves the most room for everything after it — choosing it can never hurt. This is the exchange argument to know cold: if an optimal solution's first interval isn't the earliest-ending one, swap the earliest-ending one in; it ends no later, so everything downstream still fits. "Min removals" is just n − "max selected"; "min arrows" is the same scan counting groups that share a point.

Approach: sort by end; last_end = -inf; count = 0; for each [s, e]: if s >= last_end (or >, boundary semantics per problem): take it, count += 1, last_end = e. O(n log n), O(1) extra.

What it is: Combine overlapping intervals into disjoint blocks (merge), or splice one new interval into an already-sorted disjoint list (insert). Sort by start; sweep, extending the current block while intervals touch it, emitting it when a gap appears.

Intuition: once sorted by start, an interval either overlaps the block under construction (s <= cur_end → absorb: cur_end = max(cur_end, e)) or starts a new block. The max matters: a later interval can be nested inside the block and must not shrink it. Insert (57) is merge specialized: emit all intervals ending before the new one, absorb all that overlap it, emit the rest — three phases, no sort needed.

Approach: sort by start; iterate keeping cur = [s0, e0]; overlap → extend, gap → append cur, restart. Remove-covered (1288): sort by start asc, end desc, count intervals whose end exceeds the running max end.

What it is: You advance along a line — array indices, a garden, a timeline — and each position/item extends how far you can reach. Questions: can you reach the end (feasibility), or with how few jumps/segments (optimization). One pass maintaining furthest reachable.

Intuition: you never need to decide which jump you took — only the invariant "everything up to furthest is reachable." Feasibility (55): scan i; if i > furthest you're stranded; else furthest = max(furthest, i + nums[i]). Minimum jumps (45): implicit BFS on a line — the current jump covers a window; when the scan crosses the window's end, one more jump is spent. Coverage problems (taps 1326, video stitching 1024) are the same after converting each item to an interval [i - r, i + r]: greedily pick, among intervals starting within reach, the one extending furthest. Proof: greedy maximizes furthest after every step, and any strategy's reach is ≤ greedy's (staying ahead).

Approach: feasibility: one variable. Min segments: jumps, cur_end, furthest = 0, 0, 0; for i in 0..n-2: furthest = max(furthest, i + nums[i]); if i == cur_end: jumps += 1; cur_end = furthest. Coverage-by-intervals: precompute the furthest end reachable from each start, then run the same window walk.

What it is: Two collections must be paired off — cookies to children, people into boats, your cards against theirs — optimizing matches. Sort both; walk with two pointers, always resolving the most constrained element first.

Intuition: after sorting, the extremes carry the decision. Boats (881): the heaviest person is the constraint — pair them with the lightest; if even that fails, the heaviest sails alone (no better partner will ever exist — that's the whole proof). Cookies (455): the smallest cookie that satisfies the smallest child — wasting a big cookie on an easy child can only hurt. Advantage shuffle (870): beat each of their cards with your cheapest winning card; if your best can't beat their best, sacrifice your worst against it.

Approach: sort both sides; two pointers moving inward (881: lo/hi on one array) or forward in lockstep (455). Per step: try the greedy match; on success advance both, on failure advance the constrained side only (or burn the sacrifice card). O(n log n) sort dominates.

What it is: Items must be ordered or assigned to maximize a global objective — concatenate numbers into the largest string, split people between two cities cheapest, order flowers by growing time. The entire solution is: find the pairwise comparison that says "a before b is better", sort by it, sweep.

Intuition: if a single swap of adjacent items never helps, the arrangement is optimal (any permutation is reachable by adjacent swaps). So define the comparator directly from the objective: largest number (179): a before b iff string a+b > b+a. Two cities (1029): sort by costA - costB (how much you regret sending them to A), send the first half to A — the difference, not the absolute cost, is the decision variable. Flowers (2136): sort growing time descending so long growers start earliest.

Approach: write the objective for two adjacent items in both orders, derive the inequality, hand it to the sort. Then one linear pass computes the answer. Cousin worth knowing: 406 (Queue Reconstruction) — sort by height desc, k asc, then insert each person at index k.

What it is: One pass, one accumulator (tank, profit, running sum), and a rule for when the accumulated state is worthless — reset and restart from here. The insight is always the same: a prefix that failed can be discarded wholesale.

Intuition: gas station (134): if you start at A and die at C, no station between A and C can succeed either — they'd enter C with less gas than you had. So restart from C+1; and total gas ≥ total cost ⇒ some start works. Stock I (121): the running minimum is the only past state that matters — best profit ending today = price - min_so_far. Stock II (122): with unlimited trades, every up-tick is independently collectible — answer = Σ max(0, p[i] − p[i−1]).

Approach: one loop, 2–3 variables. 134: tank, start, total; on tank < 0: start = i + 1, tank = 0; return start if total >= 0 else −1. 121: track min_price, best. 122: sum positive deltas. The entire interview is the justification.

What it is: Build the lexicographically smallest/largest result under a budget — remove k digits, keep one of each letter, choose a subsequence of length k. A stack holds the answer-so-far; each new element pops everyone it beats while the budget (removals left, duplicates available) allows.

Intuition: lexicographic order is decided at the first position of difference — so earlier positions dominate everything after. A bigger digit sitting before a smaller one should be evicted (if you may still remove) because improving an earlier position beats any later consequence. The stack stays monotonic; the budget is the only thing gating the pops. All three listed problems are one skeleton with a different pop-guard.

Approach: iterate; while stack and stack[-1] is wrong-order vs x and ⟨budget allows⟩: pop; push x (subject to its own guard — 316 skips letters already in the stack). Post-process: 402 trims leftover k from the tail and strips leading zeros; 1673 truncates to k. The transferable skill is writing the pop-guard: 402 → k > 0; 316 → last_occurrence[stack[-1]] > i; 1673 → len(stack) - 1 + (n - i) >= k.

What it is: Split a sequence into the fewest/most pieces subject to a per-piece constraint — every letter confined to one piece, no repeated character in a piece. Sweep once, tracking what the current piece still owes; cut the moment the debt hits zero (or must-cut when the constraint would break).

Intuition: two dual forms. Max pieces (763): each letter's presence obligates the piece to extend to that letter's last occurrence; maintain piece_end = max(last[c] for c seen); when i == piece_end the piece is closed and cutting immediately is safe (nothing inside is needed later, and cutting as early as possible only creates more pieces). Min pieces / forced cut (2405): extend until adding s[i] would violate (duplicate char) → start a new piece there.

Approach: 763: precompute last[c] in one pass; second pass with start, piece_end; on i == piece_end emit i - start + 1. 2405: a seen-set, reset on violation, count resets + 1. Both O(n), O(alphabet).

What it is: Decide whether a multiset of numbers can be partitioned into groups of a required shape — k consecutive cards, pairs (x, 2x), consecutive runs of length ≥ 3. Greedily consume from a canonical end (smallest first) via a hash counter: the smallest remaining element has the fewest options, so its group is forced.

Intuition: the smallest unused value can only ever be the head of its group (nothing smaller exists to precede it) — so its group is fully determined: take x, x+1, …, x+k−1 (846) or match x with 2x (954). If the forced group can't be formed, no arrangement exists (nothing else can absorb that head). 659 refines this with lookahead: prefer extending an existing run over starting a new one.

Approach: Counter + iterate values in sorted order; for each value with count > 0, consume its forced group, decrementing counters; fail fast on any missing member. 659's two-counter version: need[x] and avail[x]. O(n log n) for the sort.

What it is: Greedy where commitments are revocable: take the cheap default every time, record each decision in a heap, and when a resource runs dry (fuel, time budget, bricks), undo the single most profitable past decision and continue. Full treatment in heaps Pattern 9 — this entry places it on the greedy map.

Intuition: pure greedy fails when you can't rank present options without seeing the future; regret greedy sidesteps the lookahead by making the cheapest reversible choice and deferring the real decision to the moment of failure — when you finally have the information, one heap pop applies the best correction. The proof is still an exchange argument, applied at the failure point.

Approach: scan in the naturally-sorted order (position for 871, deadline for 630); per item take the default and push the alternative's value; on a constraint violation, pop the extreme (max-heap to undo the costliest, min-heap to downgrade the cheapest commitment) until feasible again.

What it is: Each position has a constraint involving only its immediate neighbors — more candies than a lower-rated neighbor, flowers not adjacent, correct change from what you've collected. Solve with one linear sweep (constraint looks one way) or two opposing sweeps combined with max (constraint looks both ways).

Intuition: Candy (135): "more than the left neighbor if higher-rated" and "more than the right neighbor if higher-rated" are independent one-directional constraints — satisfy each with its own directional pass, then max(left[i], right[i]) satisfies both minimally (the max of two minimums is minimal for the conjunction). Flowers (605): a slot is plantable iff both neighbors are empty right now — planting greedily left-to-right never hurts. Lemonade (860): always break a $20 with $10+$5 rather than three $5s, because $5 bills are strictly more useful (a dominance argument).

Approach: identify whether the constraint is one-directional (single pass with counters) or bidirectional (two passes + combine). 135: two O(n) passes + max. 605: single pass, mutate-or-count with sentinel empties at both ends. 860: track two counters (fives, tens), branch by bill.