Greedy Algorithms and Exchange Arguments
Concept
A greedy algorithm builds a solution one step at a time, at each step making whatever choice looks best right now and never reconsidering it. That is the entire algorithm — no backtracking, no lookahead, no exploring alternatives. The catch is that "locally best" and "part of a globally optimal solution" are different claims, and greedy only produces a correct answer on problems where a specific structural property holds: the greedy-choice property (some locally optimal choice is always safe to make first, without ruling out an optimal solution) combined with optimal substructure (an optimal solution to the whole problem contains optimal solutions to the remaining subproblem after that choice).
Having those properties isn't obvious from a problem statement — it has to be proven, and the standard proof technique is the exchange argument. The shape of the argument: assume some optimal solution OPT differs from the greedy solution G at the first point they diverge. Show that swapping OPT's choice at that point for G's choice produces another solution that is no worse than OPT — still feasible, still at least as good on the objective. Repeating this swap step by step morphs OPT into G without ever decreasing quality, which proves G is itself optimal. This is a proof by exchange, not by induction on the algorithm's steps — it reasons about the space of possible solutions, not about the algorithm's execution trace.
Classic problems where the exchange argument goes through cleanly: interval/activity scheduling (always pick the interval that finishes earliest among remaining candidates), Huffman coding (always merge the two lowest-frequency nodes), and minimum spanning tree via Kruskal's (always add the cheapest edge that doesn't create a cycle) or Prim's (always extend the tree via the cheapest crossing edge). Dijkstra's shortest-path algorithm is also a greedy algorithm under the hood — it repeatedly finalizes the closest not-yet-finalized vertex — which is why it fails on graphs with negative edge weights: the exchange argument that justifies it depends on edge weights being non-negative.
Tradeoffs
| Approach | Benefit | Cost |
|---|---|---|
| Greedy (with proven exchange argument) | O(n log n) typical (dominated by a sort or heap), simple to implement and reason about once proven | Only correct on problems with the greedy-choice property — applying it elsewhere silently gives a wrong, not just suboptimal, answer |
| Dynamic programming | Correct on a strictly larger class of optimization problems, including ones where greedy fails (e.g. non-canonical coin systems, 0/1 knapsack) | Higher time/space complexity (typically polynomial in the state space, not linear/log-linear); more implementation surface |
| Exhaustive search / backtracking | Always correct, needs no structural proof | Exponential in the general case — infeasible past small inputs |
The practical decision isn't "greedy vs. DP" in the abstract — it's "can I find (or rule out) an exchange argument for this specific problem." A problem that looks greedy but lacks the property is usually a DP problem in disguise; recognizing which one you're facing before writing code is the actual skill being tested.
When to use / when not to
- Use greedy once you've either found a known exchange-argument proof for the exact problem shape (interval scheduling, MST, Huffman-style prefix codes) or constructed your own quick proof sketch for a novel problem.
- A strong heuristic before trusting greedy: try to construct a counterexample first. Spend a few minutes actively trying to break the greedy choice with a small adversarial input. If you can't, that's weak evidence for (not proof of) correctness — but if you can, greedy is wrong and no further optimization of the greedy rule will fix it.
- Don't use greedy on 0/1 knapsack (picking items by best value-to-weight ratio first is a well-known trap — it fails on inputs where a slightly-worse-ratio item unlocks a much better combination) or on coin-change with an arbitrary (non-canonical) denomination set, e.g. coins
{1, 3, 4}making change for 6: greedy takes 4+1+1 (3 coins) when 3+3 (2 coins) is optimal. - Don't reach for greedy just because a problem asks for a "minimum" or "maximum" — that phrasing fits DP and exhaustive search equally well; it says nothing about whether the greedy-choice property holds.
Common pitfall
Treating "I ran it on the sample inputs and got the right answer" as validation. Sample inputs in a problem statement are rarely adversarial enough to expose a broken greedy rule — the 0/1 knapsack and non-canonical coin-change traps above both produce correct-looking answers on many inputs and only fail on specifically constructed ones. The only reliable validation is the exchange-argument proof itself (or a rigorous exchange-argument-style informal justification); passing test cases is evidence of not having found a counterexample yet, not evidence of correctness.
Engineering Lens
The exchange argument is worth internalizing as a general skill, not a one-off proof technique for a handful of textbook problems: it's the difference between "I have an algorithm that seems to work" and "I can state exactly why no other choice at this step could do better." In an interview or design-review setting, narrating the exchange argument (even informally — "suppose the optimal solution didn't make this choice first; here's why swapping it in doesn't hurt") is a much stronger signal than reciting a memorized greedy algorithm, because it's the part that transfers to a genuinely new problem. In production code, the same discipline shows up any time a system makes an irrevocable local decision under the assumption that it can't be beaten later — a scheduler assigning the next job, a load balancer picking the next backend, a cache eviction policy choosing what to drop. Whenever a system commits to a choice without any ability to reconsider it, the greedy-correctness question ("is this locally-best choice provably safe?") is exactly the same question, just embedded in infrastructure instead of an algorithms problem.