How Do You Prove a Greedy Algorithm is Correct?
Learn the exchange argument and greedy-choice property used to prove greedy algorithms correct, with worked interview examples.
Expected Interview Answer
Greedy algorithm correctness is typically proven with the exchange argument (show any optimal solution can be transformed into the greedy solution without losing optimality) or by proving the problem exhibits the greedy-choice property plus optimal substructure, meaning a locally optimal first choice never prevents reaching a globally optimal solution.
The exchange argument works by taking an arbitrary optimal solution, finding a place where it differs from the greedy choice, and showing you can swap in the greedy choice without making the solution worse — repeating this until the optimal solution matches the greedy one proves they are equally good. The greedy-choice property states that a globally optimal solution can be reached by making a locally optimal choice at each step, and optimal substructure means an optimal solution to the problem contains optimal solutions to subproblems. Both conditions must hold; many problems look greedy but fail one, like 0/1 knapsack, where greedy by value-density is not optimal. Classic provably-correct greedy algorithms include Kruskal's and Prim's MST algorithms, Huffman coding, and activity selection by earliest finish time.
- Exchange argument gives a rigorous, reusable proof pattern
- Confirms greedy-choice property before trusting a heuristic
- Explains why some greedy-looking approaches actually fail
- Underlies MST, Huffman coding, and scheduling algorithms
AI Mentor Explanation
A captain always sends in the batter with the best current form first, claiming this maximizes the innings score. To prove this is actually optimal, imagine any other batting order that scores just as well, then show you can always swap the in-form batter earlier without lowering the total score. Repeating that swap until the order matches the captain's choice proves greedy is at least as good as any alternative. This swap-and-compare method is exactly the exchange argument used to prove greedy algorithms correct.
Step-by-Step Explanation
Step 1
State the greedy rule precisely
Define exactly what "locally best" means at each step, e.g. earliest finish time or highest value density.
Step 2
Assume an optimal solution differs
Take any optimal solution and find the first point where it diverges from the greedy choice.
Step 3
Apply the exchange argument
Show swapping in the greedy choice at that point does not make the solution worse.
Step 4
Conclude by induction
Repeating the exchange transforms any optimal solution into the greedy one, proving greedy is optimal.
What Interviewer Expects
- Name the exchange argument as the standard proof technique
- State both required conditions: greedy-choice property and optimal substructure
- Give a correct example (activity selection, Kruskal, Huffman) and a counterexample (0/1 knapsack)
- Explain why greedy fails on 0/1 knapsack despite looking similar to fractional knapsack
Common Mistakes
- Assuming greedy works just because it "seems intuitive" without proof
- Confusing greedy-choice property with optimal substructure as the same thing
- Applying value-density greedy to 0/1 knapsack, where it is not optimal
- Not being able to state the exchange argument when asked to justify correctness
Best Answer (HR Friendly)
“To prove a greedy algorithm is correct, I use the exchange argument: I take any optimal solution and show I can always swap in the greedy choice without making it worse, which means greedy is at least as good as optimal. I also check the problem actually has the greedy-choice property and optimal substructure, since not every problem that looks greedy actually is, like 0/1 knapsack.”
Code Example
def activity_selection(activities):
# activities: list of (start, finish)
# Greedy rule: always pick the activity with the earliest finish time
activities.sort(key=lambda a: a[1])
selected = [activities[0]]
last_finish = activities[0][1]
for start, finish in activities[1:]:
if start >= last_finish:
selected.append((start, finish))
last_finish = finish
return selected
# Provably optimal via exchange argument: any optimal solution can be
# transformed to start with the earliest-finishing activity without
# reducing the total number of activities selected.
acts = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10)]
print(activity_selection(acts)) # [(1, 3), (4, 7), (8, 10)]Follow-up Questions
- Why does greedy fail on the 0/1 knapsack problem?
- How would you prove Kruskal’s algorithm produces a minimum spanning tree?
- What is the difference between greedy-choice property and optimal substructure?
- Can you give a problem where a greedy approach looks correct but is not?
MCQ Practice
1. What is the standard proof technique for greedy algorithm correctness?
The exchange argument shows any optimal solution can be transformed into the greedy solution without losing optimality.
2. Which condition, along with the greedy-choice property, is required to prove greedy correctness?
Optimal substructure means an optimal solution contains optimal solutions to its subproblems, required alongside the greedy-choice property.
3. Why does a greedy value-density approach fail on 0/1 knapsack?
Unlike fractional knapsack, items cannot be split, so a greedy pick can leave no room for a better overall combination.
Flash Cards
What is the exchange argument? — A proof technique showing any optimal solution can be transformed into the greedy solution without losing optimality.
What two conditions must a problem satisfy for greedy to be correct? — The greedy-choice property and optimal substructure.
Name a greedy algorithm with a provable correctness proof. — Activity selection by earliest finish time, or Kruskal’s MST algorithm.
Why does greedy fail on 0/1 knapsack? — Items cannot be split, so a locally optimal pick can block a better globally optimal combination.