When greedy lies to you
Greedy is seductive. The code is short, the cost is O(n log n), and it feels obviously right, but feeling right is not an argument.
The classic trap is coin change with a coin system that is not the US one. Take coins [1, 3, 4] and an amount of 6.
- Greedy takes 4, the biggest that fits, then 1, then 1, for three coins.
- The optimum is 3 + 3, for two coins.
Taking the 4 looked best and poisoned the future, because the remaining 2 can only be made with pennies.
That is the general failure mode. Greedy breaks whenever a locally best choice can damage later options and no exchange argument can rescue it.
The professional workflow is two steps: propose the greedy rule, then hunt hard for a counterexample.
Finding one means you need backtracking from unit 6 or dynamic programming from unit 9, which solves exactly this coin problem. Failing to find one, with an exchange argument to back it up, means greedy it is.
Greedy against exhaustive search
One counts coins biggest-first, the other tries every first coin and keeps the cheapest.
def greedy_coins(cents, coins): count = 0 for coin in sorted(coins, reverse=True): count += cents // coin cents %= coin return count if cents == 0 else None def best_coins(cents, coins): if cents == 0: return 0 best = None for coin in coins: if coin <= cents: sub = best_coins(cents - coin, coins) if sub is not None and (best is None or sub + 1 < best): best = sub + 1 return best print(greedy_coins(6, [1, 3, 4])) print(best_coins(6, [1, 3, 4]))
Output
3 2
They disagree, and that disagreement is the whole lesson. Greedy returns 3 and the honest answer is 2.
greedy_coins replaces the inner while loop from lesson 8-1 with cents // coin and cents %= coin, which is the same repeated subtraction done arithmetically.
Its return count if cents == 0 else None handles the case where greedy gets stuck entirely, such as coins [3, 4] and an amount of 5, where a leftover remains.
best_coins is unit 5 style recursion with no shortcuts. It tries every coin as the first move and keeps the cheapest complete answer, which is slow but honest.
None propagates through it as "no solution from here", which is why the check is sub is not None before comparing.
The cost is the catch. best_coins is exponential and re-solves the same amounts repeatedly, which is precisely the situation lesson 5-3 diagnosed, and unit 9 fixes it with a table.
Give an exchange argument, after failing to find a counterexample.
The exchange argument is the standard of proof from lesson 8-1: swapping the greedy choice into any optimal solution keeps that solution optimal.
Testing on examples is necessary and not sufficient. Examples can only falsify, so passing ten of them says nothing, and coins [1, 3, 4] would have passed a test on amount 8.
Sorting is not evidence either. It is preprocessing, and both the correct meeting rule and the broken coin rule involve sorting.
In interviews you rarely give a formal proof. What you must do is sketch the exchange in one or two sentences and show you probed for counterexamples, which signals you know the rule needs justification at all.
The habit that makes this fast is trying small adversarial inputs first. Two or three elements, values chosen so the greedy choice consumes something the optimum needed.
content_children
A greedy that works. Each child has an appetite, and each cookie satisfies a child only if it is big enough.
def content_children(appetites, cookies): appetites.sort() cookies.sort() child = 0 for cookie in cookies: if child < len(appetites) and appetites[child] <= cookie: child += 1 return child print(content_children([1, 2, 3], [1, 1])) print(content_children([1, 2], [1, 2, 3]))
Output
1 2
child does double duty. It counts satisfied children and points at the next unsatisfied one, which works only because both lists are sorted.
The loop runs over cookies rather than children, which is the choice that makes the code short. Each cookie is offered once to the easiest remaining child and then discarded.
A cookie too small for the easiest remaining child is useless to everyone, since every other child wants at least as much, so skipping it loses nothing.
That is the exchange argument here. Whatever cookie the optimum gave a child, exchanging it for the smaller one this code chose still satisfies that child, and it leaves the larger cookie available.
The first call satisfies one child, since two size-1 cookies can only feed the appetite-1 child and the second is wasted. The second call satisfies both children with the 1 and the 2, leaving the 3 unused.
Note that both lists are sorted in place, which mutates the caller's input. Using sorted() instead would be the polite version.
The difference is whether the greedy choice can damage what remains.
In cookies, giving a child the smallest workable cookie never hurts any later child, so an exchange argument goes through. The cookie you did not use is larger, and a larger cookie is never worse for anyone.
In coin change, taking the biggest coin can poison the remaining amount. Taking the 4 from 6 leaves 2, which the remaining coins handle badly, and no swap repairs it.
The test is always the same question. Can the greedy choice be swapped into some optimal solution without making it worse?
For cookies the answer is yes, and the swap is concrete. For coins the [1, 3, 4] counterexample at amount 6 kills every exchange argument outright, since the optimal solution uses no 4 at all.
The structural tell is how choices interact. Cookie choices are independent, in that using one cookie does not change what the others can do, and coin choices are coupled through the remaining amount.
When the exchange fails, you escalate to dynamic programming, which is the next unit.
Greedy uses three coins, taking 4 and then 1 + 1, while the optimum is 3 + 3 for two.
Greedy grabs the 4 first because it is the biggest coin that fits. That leaves 2, and with coins of 1, 3, and 4 available, only pennies can cover it.
The optimum ignores the 4 entirely. That is what makes this counterexample sharp, since no exchange argument can start from a choice the optimal solution never makes.
The failure needs the coin system to be uncooperative. US coins work greedily because each denomination divides cleanly into the larger ones, and [1, 3, 4] breaks that.
Memorize this tiny counterexample. It is the fastest way to show an interviewer you know greedy needs justification, and it is the exact problem dynamic programming solves correctly in unit 9.