Greedy

A greedy algorithm makes the locally best choice at every step and never revisits it — no backtracking, no keeping a table of alternatives the way DP does. That makes greedy solutions cheap when they work (usually a single O(n) or O(n log n) pass), but it also means greedy is the one technique in this course where "it feels right" is not evidence. A greedy strategy is either provably correct or it's just a guess that happens to pass a few examples — the gap between those two is an exchange argument: showing that any solution which deviates from the greedy choice can be transformed into one that follows it, without getting worse.

Why greedy needs proof, not intuition

Best Time to Buy and Sell Stock II is a clean example. The greedy rule — capture every positive day-over-day gain — sounds almost too simple. The exchange argument: any longer upward run's total gain equals the exact sum of its individual daily gains, so splitting a run into single-day buy/sell pairs never loses anything, and skipping a positive day-over-day gain can only lose profit. Assign Cookies has a similar argument: handing a big cookie to a child who doesn't need it can never help, because it either satisfies that child (which a smaller cookie could have done just as well) or fails to help while removing a cookie that a greedier child needed. In both cases, the greedy rule wins because deviating from it is provably never better — not because it "seems reasonable."

Pattern: one running value across a single pass

The cheapest greedy shape tracks exactly one piece of state and updates it once per element. Best Time to Buy and Sell Stock tracks the lowest price seen so far and checks the profit if selling today. Jump Game tracks the furthest index reachable so far. Gas Station tracks a running tank total and resets the candidate starting station the moment that tank goes negative — the exchange argument there is subtle: if the tank goes negative arriving at station i having started from some earlier station, every station between that start and i is disqualified too, since starting later only forfeits some of the positive contributions already banked. That's what makes a single pass enough instead of retrying every station independently.

Pattern: sort first, then pair from both ends

Some greedy problems only become tractable after sorting exposes the right pairing. Assign Cookies walks the least-greedy child against the smallest cookie in sorted order. Boats to Save People sorts by weight and always tries pairing the heaviest remaining person with the lightest remaining person — the heaviest person must ride in some boat regardless of who joins them, so pairing them with whoever is most likely to fit is never worse than any other pairing choice.

Pattern: track a feasible range instead of one exact value

Valid Parenthesis String looks like it needs backtracking — a * could be (, ), or nothing, and trying all three per wildcard branches exponentially. The greedy fix: track the range [lo, hi] of possible unmatched-open-paren counts, where lo assumes every * so far was a close and hi assumes every one was an open. One pass, one range, no branching — the range collapses the exponential number of individual interpretations into two numbers that summarize all of them at once.

Pattern: a monotonic stack for "smallest valid ordering"

Remove Duplicate Letters needs the lexicographically smallest ordering that still keeps every letter's relative order intact. The greedy rule: build a stack, and before pushing a new letter, pop the stack's top letter if it's larger than the new one and it reoccurs later in the string. That last condition is what makes popping safe — without checking that the popped letter still has a future occurrence, popping it could permanently lose it from the result.

When one direction isn't enough: Candy

Candy is the topic's clearest counter-example to "greedy means one simple pass." Every child needs more candy than a lower-rated neighbor on either side, and a single left-to-right (or right-to-left) pass can only ever see one of those two directions. The fix is two passes: enforce the left-neighbor constraint scanning forward, then enforce the right-neighbor constraint scanning backward, taking the max of what each pass computed rather than letting the second pass overwrite the first. Neither pass alone knows about the other's requirement, so combining them with max is what makes both constraints hold simultaneously.

Common mistakes

• Trusting a greedy idea without an exchange argument — a rule that fits a couple of examples isn't yet a proof; Gas Station and Candy are exactly the two problems in this topic where the "obvious" first guess is wrong.
• Spending a flexible resource before a rigid one — Lemonade Change's $10 bill is useless as change except when paired with exactly one $5, while a $5 can complete change for either denomination; spending the $10 first (when available) preserves more future options.
• Enforcing only one direction of a two-directional constraint — Candy's rating comparisons look both left and right; a single pass structurally cannot see both at once, no matter how it's written.
• Re-deriving reachability from scratch at each index — Jump Game and Jump Game II only need the single best (furthest) reach discovered so far; tracking anything more (like which specific earlier index produced it) is unnecessary bookkeeping.