Greedy Algorithms7 min read

Greedy Pattern

Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
typical sort + scan:Fast · \(O(n \log n)\)proof technique:Exchange argumentvs DP:Greedy commits; DP explores all choices

Imagine you're at a pizza party and you always grab the biggest slice available. Sometimes that's the perfect strategy — you end up with the most pizza. Other times, a huge slice is so awkward to hold that you'd have done better grabbing two medium ones.

That's greedy in a nutshell: make the locally best choice at every step, and hope those local wins add up to a global win. When they do, you get a beautifully simple, fast algorithm. When they don't — you need Dynamic Programming.

When Does Greedy Actually Work?

A greedy algorithm is guaranteed to work when the problem has two properties:

Greedy-choice property: There's always a globally optimal solution that includes the greedy choice. You never need to second-guess yourself — the best-looking local option is safe to commit to.

Optimal substructure: After making the greedy choice, the remaining problem has the same structure, and an optimal solution to it combines with your choice to give a globally optimal answer.

Both of these together mean you can march forward greedily without ever backtracking.

Decision tree: does greedy work for this problem?

A Tale of Two Knapsacks

Fractional Knapsack (greedy works): You have gold dust, silver flakes, copper powder. You can take any fraction. Always grab the most valuable material per gram first. Because you can perfectly fill every remaining gram with whatever is best, the greedy choice is always safe.

0/1 Knapsack (greedy fails): Same items, but now they're solid gold bars — all or nothing. Taking the highest value-per-kilo bar might leave a gap in your backpack that nothing else fits into. Two cheaper bars together might have been worth more. Greedy gets tricked by the gaps it creates.

Proving Greedy Correct: The Exchange Argument

The standard proof template for greedy correctness is the exchange argument. It goes like this:

Suppose an optimal solution OPT makes a different first choice than greedy. Find the first place they differ — greedy picks G, OPT picks something else A. Show that swapping A for G in OPT doesn't make things worse. Now OPT and greedy agree on the first choice. Keep swapping until OPT becomes identical to the greedy solution. Since each swap was non-worsening, greedy is also optimal.

Greedy vs Dynamic Programming

Both need optimal substructure. But DP explores all choices and combines sub-solutions — it's like a chess grandmaster thinking 10 moves ahead. Greedy commits to one choice and never looks back — it's like an expert who instantly knows the right move without calculating.

A practical rule of thumb: if the problem involves a continuous resource or a natural ordering (finish times, value ratios, deadlines), try greedy first. If the choices interact in complex, all-or-nothing ways, reach for DP.

Note: Greedy works for Fractional Knapsack, Interval Scheduling, Huffman Encoding, and MSTs — all because an exchange argument shows the greedy choice is never a mistake. If you can construct a counterexample, you need DP.

Greedy vs DP — Coin Change Counterexample

# Greedy works for standard coin denominations (25, 10, 5, 1)
# but FAILS for arbitrary denominations!


def greedy_change(coins, amount):
    coins.sort(reverse=True)
    result = []
    for c in coins:
        while amount >= c:
            result.append(c)
            amount -= c
    return result


# Works fine with standard coins
print(greedy_change([25, 10, 5, 1], 30))  # [25, 5]


# FAILS with coins [12, 10, 1] and amount 20
# Greedy: 12 + 1+1+1+1+1+1+1+1 = 9 coins
# Optimal: 10 + 10 = 2 coins!
print(greedy_change([12, 10, 1], 20))     # [12, 1, 1, 1, 1, 1, 1, 1, 1]
print("Optimal:", [10, 10])               # 2 coins!
Output
[25, 5]
[12, 1, 1, 1, 1, 1, 1, 1, 1]
Optimal: [10, 10]

Complexity

⚡ Typical greedy (sort + scan)Sort by the right criterion once, then one linear scan
Sorting dominates\(O(n \log n)\)
➡️ Greedy scan (after sort)One left-to-right sweep making greedy choices
Linear pass\(O(n)\)
🧩 DP alternativeMore powerful when greedy's local choice isn't safe
Polynomial\(O(n^2)\) or \(O(n·W)\)
📝 Exchange argument proofThe proof costs nothing at runtime — it just tells you the algorithm is right
Correctness proof only\(O(1)\) overhead

Quick check

You want to prove a greedy algorithm is correct. What is the exchange argument?

Continue reading

Interval Scheduling
Book as many non-overlapping meetings as possible — always pick the one that ends earliest
→
DP Pattern
Never solve the same puzzle piece twice — write it down and look it up next time
→
Fractional Knapsack
Filling a backpack with gold dust — take the most valuable per gram first
→
Huffman Encoding
Give shorter Morse code to the letters you use most — save space on every message
→