Greedy is easy to code and hard to justify

This is the keystone of the series, and it's the one I'm least comfortable handing you a recipe for — because greedy, more than any other pattern, refuses to be a recipe.

The series opened with a confession: for a long time my reflex was dynamic programming on everything. Correct, overbuilt, no feel for the lighter tool. The question that fixed it was do the choices interact? If the best move now can constrain a future move, you must remember state — that's DP. If it can't, the local best is the global best and one pass suffices — that's greedy. Greedy is what's left when you can prove the choices don't interact.

That word — prove — is the whole post. Everywhere else in the series, the proof obligation is mild. Here it's the entire job.

The trap: a rule that happens to pass

Here is how greedy goes wrong, and it's not a coding bug. You look at a problem, you guess a plausible rule — "always take the biggest," "always move the shorter side," "sort by end time" — you run it, it passes the cases you tried, you ship it. It might even be correct. But you don't know it's correct, and on the next problem the same posture produces a rule that's subtly wrong, and you can't tell the two situations apart because in both cases the loop looked clean and the small cases passed.

The clean loop is a liar. The loop is never the hard part of greedy. The hard part is the sentence you didn't write down: why can't this choice hurt me later? When you can't answer that, you don't have a greedy algorithm, you have a guess that hasn't been falsified yet.

The exchange argument

So: how do you prove the best choice now won't hurt you later? I asked this exact question while learning, because the rules everyone handed me were unjustified. The answer is a proof shape called the exchange argument, and it's the single most useful thing in this entire series for greedy.

The shape is this. Suppose there exists some optimal solution — call it OPT. You don't know what it is; you just assume one exists. Now suppose OPT disagrees with your greedy algorithm at the first place they differ: at step X, greedy picks g, but OPT picks something else, o. Your job is to show you can exchange o for g inside OPT — swap your choice in — and end up with a solution that is no worse than OPT was.

If you can always do that swap, you've won, and here's why. OPT was optimal. Your modified version is no worse than OPT, so it's also optimal — and it now agrees with greedy at step X. Repeat the argument at the next disagreement. Each swap pushes the first disagreement one step further along without ever losing optimality. So there is an optimal solution that agrees with greedy everywhere. Which means greedy is optimal.

1. 1
   Assume an optimal solution OPT exists. You never construct it — you only reason about it.
2. 2
   Find the first step where OPT diverges from your greedy choice. Greedy says g; OPT says o.
3. 3
   Exchange o for g in OPT and argue the result is no worse than OPT was.
4. 4
   Conclude there's an optimal solution agreeing with greedy one step further. Induct: greedy is optimal everywhere.

The load-bearing move is step 3. "No worse" is doing all the work, and it's where every problem becomes its own problem — the swap argument for one greedy rule tells you nothing about the next. That's the bad news, and it's also the reason greedy can't be studied like sliding window. Let me make the swap concrete on two problems I worked through myself.

Gas station, derived rather than recited

Describe it generically: a circular route of stations. At each station you gain some fuel and spend some to reach the next. You want the one start index from which you can complete the full loop without the tank ever going negative — or a verdict that no such start exists.

The recited rule is "track a running total, and whenever it goes negative, jump the start to the next station." I want to derive that, because the jump is the whole insight and reciting it teaches nothing.

Start with the obvious brute force: try every station as a start, simulate the loop, see if you survive. That's O(n^2) and it's correct. Now look at what happens during one failed attempt. Say I start at station s, and the running tank balance first goes negative when I arrive at station f. Two things follow, and the second is the one people miss.

First, s is dead. It can't be the answer — it failed. Fine.

Second, and this is the real claim: none of the stations strictly between s and f can be the answer either. Here's the argument, and notice it's a small exchange-style argument in disguise. Pick any station m between s and f. When I drove from s, I arrived at m with some balance, and crucially that balance was non-negative — because the first time the tank went negative was at f, which is past m. So a fresh start at m begins with a tank of zero, which is less fuel than the run from s had when it passed through m. The run from s reached f and only there went negative, while carrying that extra non-negative cushion. Strip the cushion away — start fresh at m with zero — and you arrive at f even worse off. So m fails too. Every station from s up to f is rejected in one shot.

That irrevocable rejection is what collapses O(n^2) into a single O(n) pass. The moment the tank goes negative at f, I don't just abandon s; I abandon everything up to and including f, and the only remaining candidate is f + 1. I never revisit a rejected station, so the start pointer and the scan pointer each move forward only, total O(n).

One more piece, separate from the start search: a valid start exists iff total fuel across all stations is at least total cost. If the totals don't cover, no start can work, period. If they do, the single survivor of the rejection sweep is provably valid. So the algorithm computes both in the same pass.

func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
    var total = 0      // running net over the whole array: decides existence
    var tank = 0       // net since the current candidate start
    var start = 0
    for i in 0..<gas.count {
        let net = gas[i] - cost[i]
        total += net
        tank += net
        if tank < 0 {   // candidate start..i all rejected in one shot
            start = i + 1
            tank = 0
        }
    }
    return total >= 0 ? start : -1
}

The code is nine lines. The reason the tank < 0 branch is allowed to throw away a whole span of candidates is the paragraph above it, and that paragraph is the actual algorithm.

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
net  = [-2,-2,-2, 3, 3]

i=0: tank=-2 < 0 -> reject 0, start=1, tank=0   (station 0 dies)
i=1: tank=-2 < 0 -> reject 1, start=2, tank=0
i=2: tank=-2 < 0 -> reject 2, start=3, tank=0
i=3: tank= 3
i=4: tank= 6
total = 0 >= 0  ->  answer = 3

Container with most water, as the worked exchange argument

Now the one that forced me to actually learn the exchange argument, because the rule looked arbitrary until I proved it.

Generically: vertical lines of varying heights on a number line. Pick two to form a container; the water it holds is min(height) * width, where width is the distance between them. Maximize it.

Two pointers, one at each end. The greedy rule: always move the shorter pointer inward. The natural objection — the one I had — is exactly the series' refrain: don't hand me the rule, show me why moving the short side can't cost me the answer later.

So run the exchange argument. The area is bounded by the shorter of the two lines — that's the binding constraint; the taller line has slack that the water never touches. Width is at its maximum right now, at the two ends, and it only shrinks as either pointer moves in. So consider the two moves available at the current pair (L, R) where L is the shorter:

• Move the short pointer. Width drops by one; the height ceiling might rise because we abandoned the short line. Upside is possible.
• Move the tall pointer. Width drops by one, and the area is still capped by the same short line L (the new tall line is either still taller, so L binds, or shorter, so it binds even lower). The height ceiling cannot rise above L. So every container formed by keeping L and pulling R inward has width strictly less than the current pair and height at most L — it is dominated by the pair we already measured.

That last bullet is the exchange. Every option we discard by not moving the tall pointer is provably no better than a pair we've already accounted for. We aren't gambling that the short-pointer move is good; we're proving the alternative throws away only dominated options. Suppose OPT uses some pair that we'd only have reached by moving the tall pointer while L was the short side — by the domination above, that pair's area is ≤ the area at (L, R), so swapping in our measured pair is no worse. The swap is always available, so the short-pointer rule is safe.

func maxArea(_ height: [Int]) -> Int {
    var l = 0, r = height.count - 1, best = 0
    while l < r {
        best = max(best, min(height[l], height[r]) * (r - l))
        if height[l] < height[r] { l += 1 } else { r -= 1 }  // abandon the binding (shorter) side
    }
    return best
}

This pairs with the converging-pointers idea in two pointers; the difference is that here the direction of the move is itself the greedy decision, and the exchange argument is what licenses it.

The honest meta: greedy can't be templated

Here's the opinion the rest of the series builds toward. Greedy has the highest insight-to-template ratio of any pattern. There is no greedy template the way there's a sliding-window template — because the reusable thing in greedy isn't code, it's a per-problem safety invariant that you have to invent and then prove with an exchange argument. The proof doesn't carry across problems. Only the proof shape does.

What little structure exists comes as loose families, and the transfer is real only within a family:

Inside a family the insight moves; across families it evaporates. That's why I think greedy can't be drilled like sliding window or absorbed like DP, where the work is mostly in defining state once and reusing the recurrence shape. With greedy you build intuition by volume, because each problem makes you re-derive its own invariant. I consider it the hardest pattern in the set for precisely this reason — it sits closer to mathematical intuition than to engineering. You don't pattern-match your way to a greedy solution; you conjecture a rule and then try to break it with an exchange argument, and you either succeed (it was wrong) or fail (it was right).

Problems to practice