Proving greedy and when it fails

Why it matters

A greedy algorithm that passes your sample tests can still be wrong. The sample tests are usually small and friendly, and a rule that fails only on rare inputs will often pass them. Interviewers know this. After you describe a greedy rule, they ask "why does this work?", and they expect a reason, not a hunch. Some of them also ask for a case where your rule fails, to see whether you test your own ideas.

This lesson gives you the two standard ways to justify a greedy rule, a method for hunting counterexamples, and a set of examples where greedy fails. By the end you should be able to take any new rule, argue for it or break it, and say which of the two you have done.

Words you will need

• Proof: a sequence of steps, each following from the last, that shows a claim must be true for every input.
• Counterexample: one specific input for which a rule gives a wrong answer. A single counterexample is enough to kill a rule.
• Exchange argument: a proof that takes any best answer and changes it, one swap at a time, into the greedy answer without making it worse.
• Stays ahead: a proof that shows, after each greedy step, the greedy choice is at least as good as any other method's choice at the same step.
• Invariant: a statement about the state of a program that stays true after every step of a loop.
• Brute force: trying every possible answer and keeping the best. It is slow, but it is a reliable reference for checking a faster method on small inputs.
• Dynamic programming: solving a problem by solving its smaller parts once, writing each answer in a table, and reusing the table. Module 26 covers it fully, and this lesson uses it as a checker.
• Dijkstra's algorithm: a method for finding the shortest path from one node to every other node in a graph. It is greedy: it always finishes the closest unfinished node.
• Negative edge: a connection in a graph whose cost is below zero. Some greedy methods fail when these exist.

The problem with trusting a rule

Here is a common story. A student writes a greedy rule, tries it on the sample input, gets the right answer, and submits. The judge says wrong answer on test 14. The student tries another sample and gets the right answer again. The rule was never proved, so the student had no way to know it was wrong.

Samples are a poor check for greedy. They are small and often hand-picked to show the idea. A rule that is subtly wrong can match every one of them. A rule that is right will match all of them too. So a matching sample tells you almost nothing. What you need is a reason, and the two methods below give you one.

There is also a trap in random testing. If you test your rule on large random inputs and it always passes, you may be tempted to trust it. But a wrong rule usually fails on small, specific inputs, which random large inputs rarely produce. So the right way to test a greedy rule is to try small cases on purpose, and to write a brute force checker for them. Program 3 in this lesson does exactly that.

Method one: the exchange argument

The exchange argument is the standard proof for greedy choices. It has three steps.

1. Take any best answer. Call it the optimal answer. You do not know what it is, but you know it exists and is at least as good as any other answer.
2. Look at its first choice. If that choice is the greedy choice, you are done with this step. If not, swap it for the greedy choice, and check that the answer is still valid and no worse.
3. Once the first choice is the greedy one, the rest of the answer solves a smaller copy of the problem. Apply the same argument again, and the whole answer becomes the greedy answer.

The point is that a swap that does not make things worse proves the greedy answer is best, because you started with a best answer and ended with the greedy answer, with the same or better value along the way.

Here is the exchange argument for activity selection, step by step. The greedy choice is the meeting G with the earliest finish time. Let the optimal answer be a set O of meetings that do not clash. If G is in O, nothing needs to change. Suppose G is not in O. Let X be the first meeting of O, which means the meeting in O with the earliest finish time. Since G has the earliest finish of all the meetings, G finishes no later than X.

Now replace X with G in O. Call the new set O'. Does O' still have no clashes? Every other meeting in O starts at or after X ends, because X was the first meeting. G ends no later than X, so every such meeting also starts at or after G ends. So G does not clash with any of them. The new set has the same size as O, so it is still a best answer, and it contains G.

Because the new best answer contains G, the greedy choice is safe. The remaining problem is the set of meetings that start at or after G ends, and the same argument applies to it. By repeating the argument, the greedy algorithm reproduces a best answer one meeting at a time.

Notice what the proof needed. It needed G to finish no later than any other meeting, which is the sort. It needed the swap to keep the answer valid, which follows from G finishing early. Those two facts are the entire content of the proof. When you write your own argument, look for the same two parts: a property of the greedy choice, and a swap that keeps the answer valid.

Method two: stays ahead

The second method is called staying ahead. It works well when the greedy answer is built one piece at a time, and each piece has a clear measure.

Here is the stays-ahead argument for activity selection. Let the greedy meetings in order be G1, G2, G3 and so on, sorted by finish time, and let any other valid plan have meetings H1, H2, H3 and so on, also sorted by finish time. Claim: after each step k, the finish time of Gk is no later than the finish time of Hk. If the claim holds, greedy never falls behind, so greedy picks at least as many meetings as any plan.

Prove the claim by induction. For k equals 1, G1 has the earliest finish of all meetings, so G1 finishes no later than H1. Now suppose Gk finishes no later than Hk. Hk+1 starts after Hk ends, which is at or after Gk's finish, because Gk finishes no later than Hk. So Hk+1 is a meeting that starts after Gk ends, and it was one of the candidates the greedy walk considered next. The greedy walk takes the earliest-finishing candidate after Gk, so Gk+1 finishes no later than Hk+1. The claim holds for k plus 1, which completes the induction.

Staying ahead is useful because it does not need a swap. It needs a measure, here the finish time of the k-th pick, and an argument that the greedy measure never gets worse. Use it when the exchange argument is hard to phrase, such as when the answer is a sequence.

What a proof gives you

A proof does two things for you. It tells you the rule is right, so you can write the code with confidence. It also tells you exactly where a rule could break. If you cannot complete the swap step, or the staying-ahead step, you have found the spot where a counterexample must live. So the proof attempt is itself a search for counterexamples.

In an interview, write the rule in one sentence, then give the argument in three or four sentences. You do not need a formal proof on paper. You need to show that you know which property the proof depends on.

Finding counterexamples on purpose

When you suspect a rule is wrong, search for a counterexample in small cases. Three or four items are usually enough. Follow this checklist.

1. Write the greedy rule as one sentence. For coins: take the biggest coin that fits.
2. Pick a small set of inputs, with three or four items, and make the numbers different from each other so the rule has a clear choice.
3. Run the rule by hand on each input. Then solve the same input by trying every answer.
4. If the answers differ, you have found a counterexample. Shrink it: remove items until the rule still fails, and the input is the smallest one that shows the failure.
5. If no counterexample appears after a few minutes, try the exchange or staying-ahead argument. If the argument goes through, the rule is probably right.

The smallest counterexample is the most useful one, because it is easy to check and easy to explain. A counterexample with ten items is hard to read. A counterexample with three items is something you can draw on a whiteboard.

Where greedy fails: coin change

Here is a problem that looks like it should work. You have coins of several values, and you want to make an amount using the fewest coins. The greedy rule is to take the biggest coin that fits, again and again.

With the coins 25, 10, 5 and 1, the rule is correct. These are the coins of many real currencies, and the greedy answer for any amount is the best one. But with the coins 4, 3 and 1, the rule fails. To make 6, greedy takes 4 first, then 1 and 1, which is three coins. But 3 and 3 makes 6 with two coins. So the rule is wrong for that coin set.

The coin set is the whole question. Greedy works for some sets of coins and fails for others, and no amount of testing with one set tells you about another. That is why you check the rule against the coin set in the problem.

The program below does the check automatically. It reads a coin set and a range of amounts. For each amount it computes the greedy count and the exact count, and it prints the amounts where greedy is worse. The exact count comes from dynamic programming, which fills a table of best answers for each smaller amount and reuses them.

Type the input below into the Input box and press Run. The first number is the count of coins. Next comes the list of coin values. The last number is the largest amount to test.

3
1 3 4
10

The output you should see:

amount 6: greedy uses 3, best uses 2
amount 10: greedy uses 4, best uses 3
amounts where greedy is worse: 2

The first line is the counterexample from before. The second is a second failure: 10 is 4 plus 4 plus 1 plus 1 for greedy, four coins, but 3 plus 3 plus 4 gives three. Two counterexamples in the range from 1 to 10 are enough to reject the rule for this coin set.

Read the dynamic programming function carefully, because you will meet this pattern again in module 26. The array best has one entry for each amount from 0 to the target. best[0] is 0, because making zero money takes zero coins. For each amount x, the function tries each coin c that is at most x, and asks whether using c gives fewer coins than the best so far. The entry best[x - c] is already known, because x - c is smaller than x. So each entry is computed from smaller ones, and the table is filled from the bottom up.

The visualizer above shows a table being filled. Each cell is computed from cells to its left, which is the same shape as the best array in the program. Watch for the amount 6: it is built from best[2] plus one coin of 4 or from best[3] plus one coin of 3, and the table shows the smaller value wins.

The greedyCount function does the greedy walk. It sorts the coins from largest to smallest, takes as many of each as fit with a division, and keeps the remainder. The remainder is the leftover amount after each step, and the % operator computes it. If the remainder is not zero at the end, the coin set cannot make the amount, and the function returns -1.

The picture below shows the same counterexample for amount 6.

Two rows for amount 6: greedy uses coins 4, 1 and 1, while the best answer uses coins 3 and 3

Where greedy fails: 0/1 knapsack

The second failure comes from the knapsack of lesson 2. There you could take part of an item, and the ratio rule was optimal. Now suppose each item is all or nothing. This is the 0/1 knapsack, named for the choice of 0 or 1 copy of each item.

Use the same three items as before: value 60 and weight 10, value 100 and weight 20, value 120 and weight 30. The capacity is 50. The ratio rule takes the first two items for weight 30 and value 160. The third item weighs 30, and only 20 units are left, so it does not fit. The total is 160.

The best all-or-nothing choice is the second and third items, which weigh 50 in total and are worth 220. The ratio rule is 60 short. It chose the high-ratio item first, which used room that a better combination needed.

The program below runs both methods. It takes the items in ratio order and takes each one that fits whole, which is the greedy 0/1 rule. It also finds the exact best value with a table. Type the same input as the fractional knapsack lesson, then press Run.

3 50
60 10
100 20
120 30

The output you should see:

greedy by ratio: 160
best possible:   220

The DP here is a one-dimensional table. dp[w] holds the best value that fits in a bag of capacity w, using the items seen so far. Start with all zeros, which is the answer for an empty set of items. For each item, update the table from the largest capacity down to the item's weight. The new value at w is either the old value, which means the item is not used, or the value at w minus the item's weight, plus the item's value, which means the item is used.

The inner loop runs backwards on purpose. If it ran forwards, a later capacity could read a value that already includes the current item, and the item would be counted twice. Running backwards means every read sees the table from before this item was considered, so each item is used at most once. That is the entire trick that makes this a 0/1 method.

The second visualizer shows a DP table being filled. Compare its shape with the dp array here. Each cell depends on earlier cells in the same row or the row above, and the final answer is in the last cell.

Both methods use the same item order and the same capacity, so the difference is only in the rule. The greedy version commits to each item as it comes, and the table version keeps both possibilities open until the end. That is the reason one is fast and wrong, and the other is slower and right.

Where greedy fails: shortest paths with negative edges

The third failure is in graphs. Dijkstra's algorithm is greedy. It starts at a source node, with distance zero. At each step it finishes the unfinished node with the smallest known distance, and then it uses that node to improve the distances of its neighbours. It never revisits a finished node.

That greedy step is correct when every edge has a cost of zero or more. A finished node's distance cannot be improved, because any other route would have to go through an unfinished node, and that node is already farther away. A negative edge breaks this. A route can go far away, come back with a large negative cost, and reach a node that Dijkstra has already finished, at a lower cost than it recorded.

The program below uses four nodes and four edges. The edges are: from 0 to 1 with cost 2, from 0 to 2 with cost 5, from 2 to 1 with cost -4, and from 1 to 3 with cost 1. The first part runs greedy Dijkstra. The second part runs Bellman-Ford, a slower method that handles negative edges by checking every edge several times. The program prints both answers. It takes no input.

The output you should see:

greedy Dijkstra: 0 2 5 3
Bellman-Ford:   0 1 5 2

Trace the greedy version. It finishes node 0 with distance 0. It then sees node 1 at distance 2 and node 2 at distance 5. It finishes node 1 at 2, because 2 is the smallest unfinished distance, and from there node 3 gets 3. Next it finishes node 3 at 3, then node 2 at 5. The edge from 2 to 1 would give node 1 a distance of 1, but node 1 is already finished, so the edge is ignored. The answer for node 1 stays at 2.

The true shortest distance to node 1 is 1, by the route 0 to 2 to 1, which costs 5 minus 4. Node 3 is 2 by that same route plus the last edge. The greedy answer is wrong for nodes 1 and 3. Bellman-Ford finds the right values, because it allows a later edge to lower an earlier distance.

The picture below shows the graph with the costs on the arrows.

Four nodes with edges from 0 to 1 cost 2, 0 to 2 cost 5, 2 to 1 cost minus 4, and 1 to 3 cost 1

The lesson for greedy is this. Dijkstra's greedy step relies on a property, that finished distances never improve. A negative edge breaks that property, so the algorithm's proof no longer applies. When a problem has negative edges, use Bellman-Ford instead, which is covered in module 24.

Program 3: a stress test with brute force

Stress testing means running your fast method against a slow, trusted method on thousands of small random inputs, and looking for a difference. It is how working programmers check a greedy rule before they trust it. This program does exactly that for the activity selection rule from lesson 1.

The fast method is the earliest-finish rule. The trusted method is brute force: for each small list of meetings, it tries every subset of meetings and keeps the largest subset that has no clashes. The random inputs come from a fixed generator, so the same tests run each time, which makes the output reproducible. The program prints the number of tests that disagree, and it shows the first few failures.

The program needs no input. Click Run.

The output you should see:

tests 500, mismatches 0

Zero mismatches is the right result here, because the earliest-finish rule is correct. The test does not prove that. It shows only that no counterexample appeared in 500 small cases. A proof is still needed for certainty, which the exchange argument provides. The test is a safety net that catches a wrong rule you may not have proved yet.

Look at the brute force function. It uses a bitmask: the number mask has one bit for each meeting, and bit i set means meeting i is chosen. The loop over mask visits every subset, which is 2 to the power n subsets. For ten meetings that is 1024, which is small. The test checks every pair of chosen meetings for an overlap, and it keeps the largest valid subset.

The expression ((mask >> i) & 1) reads bit i. The shift moves that bit to the last position, and the & 1 keeps only that bit. The parentheses make the order easy to read. In C++ the shift binds tighter than &, so they are not strictly needed. Brute force is slow, so the checker only runs on small inputs. That is the right trade-off, because counterexamples are almost always small.

If you change the greedy rule, for example to earliest start, this program will find a counterexample quickly. Try it: change a.finish < b.finish to a.start < b.start in the sort, and run the program again. You will see a failure reported with the test number and the two answers.

A checklist for any new greedy rule

Use these steps every time you invent a greedy rule.

1. State the rule in one sentence, including the sort key and the direction.
2. Write a stress test or a small hand check with three or four items against a brute force answer.
3. If the test finds a counterexample, shrink it, change the rule or switch to dynamic programming, and test again.
4. If no counterexample appears, write the exchange argument or the stays-ahead argument, using the greedy choice property and the optimal substructure.
5. If the argument breaks at one step, look at that step. It usually shows the exact input that fails.
6. Only then write the final code, and state the complexity.

Common mistakes

Trusting the sample. A rule that passes the sample is not proved. Hunt for a small counterexample before you trust any rule, even when the sample looks right.

Testing only large random inputs. Wrong rules often fail on tiny inputs with unusual values. A test with 10,000 random items may never produce those values. Test small cases on purpose, with brute force.

Believing greedy is always faster to write, so it must be right. A fast wrong answer is worth nothing. Speed of writing is not evidence of correctness.

Confusing the fractional and 0/1 knapsack. The same ratio rule is optimal in one and wrong in the other. Read the problem statement and check whether you may take part of an item.

Assuming a coin set works because it is familiar. Coins of 1, 5, 10 and 25 are a canonical set, where greedy works. Other sets, such as 1, 3 and 4, fail. Check the set in the problem, do not assume it.

Using Dijkstra on negative edges. The rule is greedy and fast, and it gives a wrong answer with a negative edge, without any error message.

Debugging walkthrough

Suppose a judge says your greedy answer is wrong on a hidden test. You do not know the input. Follow these steps.

First, write a brute force or dynamic programming version of the same problem. It is slower but trusted, and you can use it to get the correct answer for small inputs.

Second, run both on many small random inputs and print the first input where they differ. Shrink that input by removing one item at a time, and keep the removal if the two answers still differ. The result is a small counterexample.

Third, trace your greedy rule by hand on the small counterexample. Find the first choice where it went wrong, which is the step where a different choice would have led to a better total.

Fourth, decide whether the rule can be repaired. Sometimes a different sort key works. Often the problem needs dynamic programming. Either way, the counterexample tells you what the fix must handle.

Variations and edge cases

Canonical coins. For some coin sets, greedy is always optimal, and these are called canonical. The program above compares greedy with the exact answer over a range of amounts. For a new coin set, that comparison is strong evidence, but only a proof settles the question for every amount.

Exchange argument with ties. When two items tie on the greedy key, the exchange argument still works, because swapping one for the other gives the same value. Write the argument with the tie-breaking rule as part of the proof.

Greedy as a starting point. Some problems use greedy to find a good answer quickly, and then improve it. This is called a heuristic. A heuristic is useful, but it does not promise the best answer, so you must say so.

Conditions behind an algorithm. Dijkstra's algorithm is correct only when every edge is nonnegative. Adding one negative edge does not change the code, but it breaks the proof. Check the conditions for an algorithm, not just its name.

Interview questions you will hear

The usual question is how you know a greedy rule is correct. The answer names the exchange argument or the stays-ahead argument, states the greedy choice property, and explains the swap or the induction. The second question is for a counterexample to a rule the interviewer suggests. Build a three-item example, compute both answers, and show the difference. The third question is whether greedy is always better than dynamic programming. The answer is no. Greedy is faster when it is correct, but dynamic programming works for more problems, and a wrong greedy answer is worse than a slow correct one.

Practice

1. Easy. Find a counterexample. Is the rule "take the largest coin that fits" correct for coins 5, 4 and 1, with amount 8? Show the answers.

2. Easy. Explain a rule in one sentence. State the greedy rule for the 0/1 knapsack in one sentence, including the sort key.

3. Easy. Spot the bug in a proof. A student's exchange argument says: "Replace the first meeting of the optimal answer with the greedy meeting, and the answer is still valid." What is missing?

4. Medium. Ratio ties. Two items are (10, 5) and (6, 3). Do they have the same value per unit? Explain why a greedy walk gives the same total in either order.

5. Medium. Run the stress test with a bad rule. Change Program 3 to sort by start time instead of finish time. Predict whether the mismatches count will be zero, and explain.

6. Medium. Shrink a counterexample. Starting from the coin counterexample amount 6 with coins 1, 3 and 4, find the smallest coin set that still makes greedy fail at some amount.

7. Medium. Build a counterexample for the 0/1 rule. Give a three-item 0/1 knapsack input, with capacity 10, where the ratio rule gives a smaller answer than the best.

8. Medium. Dijkstra with nonnegative edges. Explain in two sentences why Dijkstra's algorithm is correct when every edge has a cost of zero or more.

9. Medium. Count the table work. The coin DP for amounts up to N and with C coin values does about how many steps? Explain.

10. Hard. Swap two jobs. Jobs run back to back from time 0. Job P is due at time 5 and job Q is due at time 9. Suppose a schedule runs Q first and P second. Show that swapping them never makes the largest lateness worse, which is the reason for sorting by due time.

11. Hard. Write the swap. Use the exchange argument to show that the earliest-finish meeting G can replace the first meeting X of an optimal plan, when G is not already in the plan.

12. Hard. Compare the two proofs. Explain when you would use an exchange argument and when you would use staying ahead.

What you now know

• A greedy rule needs a proof, not just a passing sample.
• The exchange argument swaps the first choice of a best answer for the greedy choice without making it worse.
• The staying-ahead argument shows the greedy choice is never behind, step by step, using induction.
• A counterexample is one input where the rule fails, and small inputs are the best place to find one.
• Greedy fails for coin sets such as 1, 3 and 4, for the 0/1 knapsack, and for Dijkstra with negative edges.
• A stress test that compares the fast rule with brute force on many small random inputs is a strong safety net.
• Dynamic programming solves problems where greedy fails, by keeping a table of answers to smaller parts.