Greedy algorithms, and when they are wrong
A greedy algorithm takes whatever looks best right now and never takes it back. No alternatives are kept, nothing is remembered, and there is only ever one pass over the problem. That is why greedy algorithms are the fastest things in the subject, and it is also the reason they can be wrong.
Below is the most familiar one there is: making change by always handing over the largest coin that fits. Start with everyday coins and it does exactly what you would do yourself, using the fewest coins possible every time.
Then press odd, which removes the 5 and changes nothing else. Not one character of the algorithm is different. It now makes 30 with 6 coins, where 3 would have done.
1function change(coins, amount) {2 const purse = []3 for (const coin of coins) { // largest first4 while (coin <= amount) { // does it fit?5 amount -= coin // take it6 purse.push(coin)7 }8 }9 return purse10}
The purse
drawn by value; faded means too big for what is left
Making 63
- 25
- 10
- 5
- 1
63 still owed
Handed over
one slot per coin, so the total is countable
0 coins
Making 63 from 25, 10, 5, 1. The rule is simple: always take the largest coin that fits.
The rule, the step that ruins everything after it, and why one failing case settles the question.
The rule, and why it is so fast
Look at the coins largest first. If one fits in what is still owed, take it and keep taking it while it fits. When it no longer does, move down a size. Stop when nothing is owed.
There is no list of possibilities anywhere, no going back, and nothing to store beyond the running total. That is the appeal: a greedy algorithm usually costs a single pass, where working out the genuinely best answer means considering combinations.
Where it breaks
Watch the odd purse make 30. The 25 fits, so it is taken, which leaves 5. There is no 5 any more, so 5 becomes five 1s, and the total is 6 coins. Three 10s were sitting there the whole time.
Nothing about that first step was careless. Taking the 25 was the locally best move: it is the largest coin that fits, it reduces what is owed more than any other single choice, and judged on its own it is unarguable. It is still the reason the answer is worse.
That is the shape of every greedy failure. Not a bad step, but a good step whose cost only appears later, when the algorithm is no longer looking.
One case is enough
Removing the 5 breaks the same code on 30 of the 99 amounts below 100, starting at 30. Drag the amount and you will find them; they are not rare.
But even one would have been enough. A rule that is right almost always is not right, and a single counterexample settles it. This is why greedy algorithms are the part of the subject where people bother with proofs: testing shows you the cases you thought of, and the coin sets that break greedy are exactly the ones nobody thinks of.
How anyone actually knows
The usual proof is an exchange argument, and it is worth seeing once because it is short. Take any best possible answer. Show that if it does not already begin with the greedy step, you can swap its first step for the greedy one without making it any worse. It follows that some best answer starts greedily, and by repeating the argument, that going greedily all the way is best.
Try it with 25, 10 and 1, and it fails on the first line. The best way of making 30 is three 10s; swapping the first 10 for a 25 leaves 5 to make from 1s, and the answer gets worse rather than staying equal. The proof breaking is not an accident of how it was written. It is the algorithm being wrong.
The ones that are provably right
Plenty of greedy algorithms survive that test, and they are among the most used pieces of code in existence.
- Choosing the most meetings that fit in a day. Always take the one that finishes earliest. It looks like it should be “shortest first” and that version is wrong.
- Huffman coding, which is inside every zip file and every JPEG: repeatedly merge the two least common symbols.
- Dijkstra's algorithm for shortest routes, which is greedy about which place to settle next, and is the reason your phone can plan a journey.
- Building a cheapest network that connects everything, by repeatedly adding the cheapest connection that joins two pieces that were not joined before.
Each of those has a proof behind it. None of them is safe by analogy with the others, and swapping the rule for one that sounds equally sensible usually breaks it.
What to do when it is not safe
Two answers, and the choice between them is usually about how much you care.
The first is to stop taking the first answer and start considering the combinations, remembering the ones already worked out so the same subtotal is never computed twice. For the coin problem that turns a single pass into a table of every amount up to the target, which is more work and always right. The next lesson is about doing exactly that.
The second is to keep greedy and know what it costs you. Many important problems have no fast exact answer at all, and for those a greedy rule with a proven bound is genuinely the best available: not correct, but never worse than some known factor, and fast enough to run.
Why it keeps catching people
Greedy code is short, readable, and usually right on the examples someone tries. There is no crash, no obviously wrong output, and the answer it gives is plausible. The coin version above is six lines and returns a perfectly valid set of coins; it is simply not the smallest set, and nothing on screen says so unless you already know the number to compare against.
Which is the practical lesson. When you reach for a greedy rule, the question is never whether the code works. It is whether anyone has proved that the locally best step is safe on the data you have.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
From coins of 25, 10 and 1, taking the largest that fits makes 30 with 6 coins, when 3 would do. What went wrong?
Coins of 25, 10, 5 and 1 make 63 in 6 coins, which is the fewest possible. Removing the 5 breaks the same code on 30 amounts under 100. What decides whether greedy works?
A greedy algorithm has just made a choice that will turn out badly. When does it find out, and what does it do about it?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Make 40 from 25, 10 and 1
Coins: 25, 10, 1.
Amount: 40.
How many coins does the greedy rule use,
and how few are possible?Show the answer →Hide the answer
Greedy: 25 + 10 + 1 + 1 + 1 + 1 + 1 = 7 coins.
Best: 10 + 10 + 10 + 10 = 4 coins.The same trap as 30. Taking the 25 leaves 15, which the purse can only finish with a 10 and five 1s.
Find a purse that is always safe
Which of these is greedy guaranteed to be
optimal for, at every amount?
A) 1, 3, 4
B) 1, 2, 4, 8, 16
C) 1, 7, 10Show the answer →Hide the answer
B.Each coin is at least double the one below it, so no combination of smaller coins can add up to more than the next size without simply being that size. A) breaks at 6: greedy gives 4+1+1, but 3+3 is better. C) breaks at 14: greedy gives 10+1+1+1+1, but 7+7 is better.
Break the meeting-room rule
You want the most meetings that fit in one room.
A tempting greedy rule is "always take the
shortest meeting still available".
Find three meetings where that gives the
wrong answer.Show the answer →Hide the answer
10:00–11:00, 10:45–11:15, 11:00–12:00.
Shortest first takes the 30-minute meeting,
which collides with both others: one meeting.
Taking the two long ones gives two.The rule that does work is 'take the one that finishes earliest', because finishing early leaves the most room for everything after it. Both rules are greedy and only one is sound, which is why the proof is the interesting part rather than the strategy.
Why the exchange argument matters
With coins 25, 10 and 1, the best way to make 30
is 10 + 10 + 10.
Swap the first coin for the greedy choice, a 25.
What happens, and what does it prove?Show the answer →Hide the answer
You are left owing 5, which needs five 1s,
so the answer becomes 6 coins instead of 3.
Swapping in the greedy step makes it worse,
so no best answer begins with it, and the
greedy rule cannot be optimal here.This is the whole proof technique, run in reverse. Where greedy is sound, that same swap always leaves you no worse off, and that single fact is what the correctness rests on.
How would you check a purse?
Given any set of coins, how would you find out
whether the greedy rule is optimal for it,
without proving anything by hand?Show the answer →Hide the answer
Compute both answers for every amount up to
some bound and compare them. If they ever differ,
greedy is unsound for that purse.This is what the tests behind this lesson do, across the whole range the slider can reach. There is also a known result that checking amounts up to a bound derived from the two largest coins is sufficient, so the question is genuinely decidable rather than only testable.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+What is a greedy algorithm?
One that takes the locally best option at every step and never reconsiders. It keeps no alternatives, which is why it is usually a single pass, and why it can produce an answer that is valid but not the best one.
+When is it safe to use one?
When the problem has both properties: some best answer starts with the greedy step, and what is left after that step is a smaller version of the same problem. The first is the one that usually fails, and the way to check it is an exchange argument.
+Give me an example where greedy fails.
Making change. With coins of 25, 10 and 1, taking the largest that fits makes 30 from a 25 and five 1s, six coins, when three 10s would do. Add a 5 to the purse and the identical code becomes optimal, which is the real point: the algorithm is not what decides it.
+So how would you solve the coin problem properly?
Work out the fewest coins for every amount from zero up to the target, where each one is one coin plus the best answer for what remains. Every subtotal is computed once and reused, which makes it a table rather than a search.
+Why use greedy at all, if it can be wrong?
Because when it is provably right it is by far the cheapest thing available, and Dijkstra, Huffman and the cheapest-network algorithms are all greedy. And for problems with no fast exact answer, a greedy rule with a proven bound is often the best that exists.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Also in this course
Big-O: what “grows faster” actually means
A greedy rule is cheap because it makes one pass. That sentence only means something once you can compare one pass with the alternatives.
Start there →