What Makes a Problem Greedy, and When Greedy Fails
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A greedy algorithm builds an answer one step at a time and always takes the choice that looks best right now. It is fast and short, but only some problems allow it. This lesson shows when it is safe and how to prove it wrong.
Greedy: take the best choice now
A greedy algorithm builds a solution step by step and, at each step, takes the choice that looks best at that moment. It never goes back to change an earlier choice.
A cashier must give change using as few notes as possible. Take the largest note that still fits, then repeat with what is left. The choice is never undone.
def make_change(amount, notes): used = [] for note in sorted(notes, reverse=True): while amount >= note: amount -= note used.append(note) return used
print(make_change(289, [100, 50, 20, 10, 5, 1]))Example 1 · Largest first works for notes of 100, 50, 20, 10, 5 and 1
notes = [100, 50, 20, 10, 5, 1]for amount in (289, 95, 7): count = 0 for note in notes: count += amount // note amount %= note print(count)10 4 3
What this code does
//counts how many whole notes fit and%keeps the rest.- For these notes the largest-first rule is always optimal, so greedy is safe. This is called a canonical coin system.
The loop sorts once and then takes each note as often as it fits. That is O(n log n) for the sort plus one step per note given.
The two conditions that make greedy correct
The greedy-choice property says that some best overall answer starts with the greedy choice, so taking that choice first never loses the best answer.
Greedy is only safe when both conditions below hold. Check them before you trust a greedy rule.
- Greedy-choice property: the best-now choice can be part of an optimal answer.
- Optimal substructure: after the choice, what remains is a smaller problem of the same kind.
- If both hold, repeating the choice reaches an optimal answer.
- If one fails, greedy may return a good-looking but wrong answer.
When greedy fails: a counterexample
A counterexample is one small input on which a rule gives a wrong answer. A single counterexample is enough to show that a greedy rule is not correct.
Now the coins are worth 1, 3 and 4, and the amount is 6. The largest coin first gives 4 + 1 + 1, which is three coins. But 3 + 3 uses only two.
def greedy_coins(amount, coins): count = 0 for coin in sorted(coins, reverse=True): count += amount // coin amount %= coin return count
print(greedy_coins(6, [1, 3, 4]))Example 2 · Dynamic programming beats greedy on coins 1, 3 and 4
def best_coins(amount, coins): best = [0] + [amount + 1] * amount for total in range(1, amount + 1): for coin in coins: if coin <= total: best[total] = min(best[total], best[total - coin] + 1) return best[amount]
print(best_coins(6, [1, 3, 4]))2
What this code does
best[total]stores the fewest coins for that total, found by trying every coin.- It costs O(amount times coins) time and O(amount) space, slower than greedy but always right.
It prints 3, but the best is 2. When greedy fails like this, try dynamic programming, which compares every choice.
How to check a greedy idea before you code
An exchange argument shows that any best answer can be changed, one swap at a time, to start with the greedy choice without getting worse. That proves the greedy choice is safe.
Try the rule on three or four tiny inputs by hand, and try to break it. Then explain why the first choice can always be swapped into any best answer.
- Write the rule in one sentence, such as "sort by end time and take the first that fits".
- Search for a small counterexample with two or three items.
- Compare against a slow brute force on random small inputs.
- Sorting is usually the first step, so the cost is often O(n log n).
Example 3 · Find the first amount where greedy fails
def greedy(amount, coins): count = 0 for coin in sorted(coins, reverse=True): count += amount // coin amount %= coin return count
def best(amount, coins): table = [0] + [amount + 1] * amount for total in range(1, amount + 1): for coin in coins: if coin <= total: table[total] = min(table[total], table[total - coin] + 1) return table[amount]
coins = [1, 3, 4]for amount in range(1, 20): if greedy(amount, coins) != best(amount, coins): print(amount, greedy(amount, coins), best(amount, coins)) break6 3 2
What this code does
- Testing a greedy rule against a slow correct version on small inputs is the fastest way to find a counterexample.
- The first mismatch is at 6, where greedy needs 3 coins and the best is 2.
Example 4 · Greedy that is correct: match students with laptops
needs = [3, 1, 2]laptops = [1, 1, 3, 2]needs.sort()laptops.sort()matched = 0for size in laptops: if matched < len(needs) and size >= needs[matched]: matched += 1print(matched)3
What this code does
- Each student needs a laptop of at least a given size. Serve the smallest need first with the smallest laptop that fits.
- Sorting both lists makes it O(n log n). A small laptop that fits nobody is simply skipped.
Next step
Check your understanding
10 quick questions