How to Prove Greedy Algorithms Correct: Exchange Argument, Induction, and Greedy Choice Property

You've written a greedy solution. It passes the examples. But in an interview, the question comes: "How do you know it's correct?"

Most developers freeze. They can code greedy, but they can't prove it works. And in top-tier interviews (Google, Meta, etc.), proof is expected.

This guide teaches you how to prove greedy correctness using four powerful techniques: exchange argument, greedy choice property, induction, and optimal substructure. With templates, examples, and step-by-step proofs.

TL;DR

Four proof techniques:

1. Exchange Argument - Show you can swap greedy choice into any optimal solution
2. Greedy Choice Property - Prove local optimal leads to global optimal
3. Induction - Prove base case + inductive step
4. Optimal Substructure - Show optimal solution contains optimal subproblems

When to use each:

• Exchange argument: Interval scheduling, activity selection
• Greedy choice property: Most greedy problems
• Induction: Reachability, state tracking
• Optimal substructure: Verify DP-like structure

Why Proving Greedy Correctness Matters

Interview Expectations

At FAANG companies:

• ✅ Code the solution (30% of credit)
• ✅ Explain why it works (30% of credit)
• ✅ Prove correctness (40% of credit)

Without proof:

• Interviewer: "How do you know this is optimal?"
• You: "Uh... it seems to work?"
• Result: No hire ✗

With proof:

• Interviewer: "How do you know this is optimal?"
• You: "By exchange argument: any optimal solution can be transformed to include the greedy choice..."
• Result: Strong hire ✓

Avoiding Wrong Solutions

Greedy without proof:

# Coin Change - greedy approach
def coinChange(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

# Seems to work... but FAILS on [1,3,4], amount=6
# No proof → didn't catch the bug

Greedy with proof attempt:

Claim: Taking largest coin first is optimal
Proof attempt: ...
  Wait, counterexample: [1,3,4], amount=6
  Greedy: [4,1,1]=3, Optimal: [3,3]=2
  Proof FAILS → caught the bug! ✓

Proof Technique 1: Greedy Choice Property

Definition

Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice.

In other words: The greedy choice is always part of some optimal solution.

Template

1. Define the greedy choice
2. Assume there's an optimal solution OPT
3. Show that if OPT doesn't include the greedy choice,
   we can modify it to include the greedy choice
4. Prove the modified solution is still optimal
5. Conclude: greedy choice is safe

Example: Activity Selection

Problem: Select maximum non-overlapping activities.

Greedy choice: Pick activity that ends earliest.

Proof:

Step 1: Define greedy choice

• Let g = activity with earliest end time among all activities

Step 2: Assume optimal solution

• Let OPT = {a₁, a₂, ..., aₖ} be an optimal solution
• Assume activities sorted by end time

Step 3: Consider two cases

Case 1: g ∈ OPT (g is in optimal solution)

• Greedy choice is already in OPT ✓

Case 2: g ∉ OPT (g is not in optimal solution)

• Let a₁ be the first activity in OPT
• Since g has earliest end time: end(g) ≤ end(a₁)
• Replace a₁ with g in OPT to get OPT'

Step 4: Prove OPT' is still optimal

• g ends no later than a₁
• All activities after a₁ in OPT are compatible with a₁
• Since g ends earlier, they're also compatible with g
• |OPT'| = |OPT| (same size)
• Therefore, OPT' is optimal ✓

Step 5: Conclusion

• Any optimal solution can include the greedy choice
• Greedy choice property holds ✓

Example: Fractional Knapsack

Problem: Maximize value in knapsack (can take fractions).

Greedy choice: Take item with highest value/weight ratio.

Proof:

Step 1: Let g = item with highest v/w ratio

Step 2: Assume OPT doesn't include full amount of g

Step 3: OPT must include some other item i with lower ratio

• ratio(g) > ratio(i)

Step 4: Exchange: Replace some of item i with item g

• Remove ε weight of item i: lose ε × ratio(i) value
• Add ε weight of item g: gain ε × ratio(g) value
• Net gain: ε × (ratio(g) - ratio(i)) > 0
• Contradiction: OPT wasn't optimal ✗

Step 5: Therefore, OPT must include maximum of item g ✓

Proof Technique 2: Exchange Argument

Definition

Exchange Argument: Show that any optimal solution can be transformed into one that includes the greedy choice, without making it worse.

Key idea: "Exchange" a choice in the optimal solution with the greedy choice, prove the result is still optimal.

Template

1. Let G = greedy solution, O = optimal solution
2. If G = O, done ✓
3. If G ≠ O, find first difference
4. Exchange: Replace element in O with greedy choice
5. Prove exchange maintains optimality
6. Repeat until G = O
7. Conclude: greedy is optimal

Example: Interval Scheduling (Detailed)

Problem: Maximum non-overlapping intervals.

Greedy: Sort by end time, pick earliest-ending.

Proof:

Setup:

• G = {g₁, g₂, ..., gₖ} (greedy solution, sorted by end time)
• O = {o₁, o₂, ..., oₘ} (optimal solution, sorted by end time)
• Goal: Show k = m

Base case:

• If g₁ = o₁, both start the same ✓

Exchange step:

• If g₁ ≠ o₁, then end(g₁) ≤ end(o₁) (by greedy choice)
• Replace o₁ with g₁ in O → O' = {g₁, o₂, ..., oₘ}

Prove O' is valid:

• g₁ ends no later than o₁
• All intervals after o₁ are compatible with o₁ (no overlap)
• Since g₁ ends earlier, they're also compatible with g₁
• O' is a valid solution ✓

Prove O' is optimal:

• |O'| = |O| = m (same size)
• O is optimal, so O' is also optimal ✓

Induction:

• O' now starts with g₁ (same as greedy)
• Repeat for remaining intervals: g₂, g₃, ...
• Eventually O' = G
• Therefore |G| = |O'| = |O| = m
• Greedy is optimal ✓

Visual Exchange

Optimal O:  [----o₁----]     [--o₂--]  [--o₃--]
                ↓ exchange
Modified O': [--g₁--]         [--o₂--]  [--o₃--]

g₁ ends earlier, no new conflicts, still optimal.
Repeat exchange for o₂, o₃, ... → entire solution becomes greedy.

Proof Technique 3: Induction

Definition

Induction: Prove greedy works for base case, then show if it works for n-1, it works for n.

Template

1. Base case: Prove greedy works for smallest input
2. Inductive hypothesis: Assume greedy works for input of size n-1
3. Inductive step: Prove greedy works for input of size n
   - Make greedy choice
   - Remaining problem has size n-1
   - Apply inductive hypothesis
   - Combine to get solution for size n
4. Conclusion: Greedy works for all n

Example: Jump Game

Problem: Can you reach the last index?

Greedy: Track maximum reachable position.

Proof by Induction:

Base case (n=1):

• Array of size 1: always at the end ✓

Inductive hypothesis:

• Assume greedy correctly determines reachability for arrays of size n-1

Inductive step (size n):

• Let max_reach = maximum position reachable from indices 0..i
• At position i:
  • If i > max_reach: position i is unreachable
    • No future position can help (they're beyond i)
    • Return False ✓
  • If i ≤ max_reach: position i is reachable
    • Update max_reach = max(max_reach, i + nums[i])
    • Remaining problem: can we reach n-1 from positions i+1..n-1?
    • This is a problem of size n-i-1 < n
    • By inductive hypothesis, greedy works ✓

Conclusion:

• Greedy correctly determines reachability for all n ✓

Example: Gas Station

Problem: Find starting station to complete circuit.

Greedy: If can't reach j from i, start from j+1.

Proof by Contradiction + Induction:

Claim: If you can't reach station j from station i, you can't reach j from any station k where i < k < j.

Proof:

1. Assume cumulative balance from i to j is negative (can't reach j)
2. For any station k between i and j:
   • Balance from i to k must be non-negative (else we'd have failed earlier)
   • Balance from k to j = (balance i→j) - (balance i→k)
   • Since balance i→j < 0 and balance i→k ≥ 0
   • Balance k→j < 0
3. Therefore, can't reach j from k either ✓

Conclusion: If we fail at j, next candidate is j+1 (greedy choice is correct) ✓

Proof Technique 4: Optimal Substructure

Definition

Optimal Substructure: An optimal solution to a problem contains optimal solutions to its subproblems.

Note: This is necessary for both greedy AND DP. The difference:

• Greedy: Only solve ONE subproblem (after greedy choice)
• DP: Solve ALL subproblems

Template

1. Make greedy choice
2. Show remaining problem is a subproblem
3. Prove: If subproblem solution is optimal,
   then greedy choice + subproblem solution is optimal overall
4. Conclude: Optimal substructure holds

Example: Activity Selection

Greedy choice: Pick activity g with earliest end time

Subproblem: Select maximum activities from those starting after g ends

Proof:

1. Let S = set of all activities
2. Let g = activity with earliest end time
3. Let S' = activities starting after g ends
4. Let OPT(S) = optimal solution for S
5. Let OPT(S') = optimal solution for S'

Claim: OPT(S) = {g} ∪ OPT(S')

Proof:

• OPT(S) must include some first activity
• By greedy choice property, can assume it's g
• Remaining activities must be from S' (start after g)
• If remaining activities aren't optimal for S', we could improve OPT(S)
• Therefore, remaining must be OPT(S') ✓

Conclusion: Optimal substructure holds ✓

Applying Proofs to LeetCode Problems

Problem: Non-overlapping Intervals (#435)

Greedy: Sort by end time, count maximum non-overlapping.

Proof (Exchange Argument):

Same as activity selection:
- Any optimal solution can be transformed to include earliest-ending interval
- Greedy is optimal ✓

Problem: Jump Game (#55)

Greedy: Track maximum reach.

Proof (Induction):

Base case: Array of size 1 → always reachable ✓

Inductive step:
- If i > max_reach, unreachable (no future position can help)
- If i ≤ max_reach, update max_reach
- Remaining problem solved by induction ✓

Problem: Gas Station (#134)

Greedy: If fail at j, start from j+1.

Proof (Contradiction):

If can't reach j from i, can't reach j from any k ∈ (i,j):
- Balance i→k ≥ 0 (else failed earlier)
- Balance i→j < 0 (given)
- Balance k→j = (i→j) - (i→k) < 0
- Contradiction if we try k as start ✓

Common Proof Mistakes

Mistake 1: Circular Reasoning

❌ Wrong:

Claim: Greedy is optimal
Proof: Greedy gives the best solution
       The best solution is optimal
       Therefore greedy is optimal ✗

✅ Correct:

Claim: Greedy is optimal
Proof: By exchange argument:
       Any optimal solution can be transformed to greedy
       Without changing optimality
       Therefore greedy is optimal ✓

Mistake 2: Missing Edge Cases

❌ Wrong:

Proof: For all activities, greedy picks earliest-ending
       Therefore optimal ✗
       (What if array is empty? What if all overlap?)

✅ Correct:

Proof: 
  Edge case 1: Empty array → return 0 ✓
  Edge case 2: All overlap → greedy picks one ✓
  General case: Exchange argument shows optimality ✓

Mistake 3: Assuming Without Proving

❌ Wrong:

Claim: Taking largest coin first is optimal
Proof: Larger coins are better
       Therefore greedy is optimal ✗
       (No actual proof!)

✅ Correct:

Claim: Taking largest coin first is optimal
Proof attempt: ...
  Counterexample: [1,3,4], amount=6
  Greedy: [4,1,1]=3
  Optimal: [3,3]=2
  Claim is FALSE ✗

Proof Checklist

Before claiming greedy is correct:

• Defined the greedy choice clearly
• Proved greedy choice property OR exchange argument
• Checked for counterexamples
• Verified optimal substructure
• Handled edge cases
• Tested on examples

Practice Strategy

To master greedy proofs:

1. Solve Interval Scheduling - practice exchange argument
2. Solve Jump Game - practice induction
3. Try Coin Change - find counterexample (greedy fails)
4. Solve Fractional Knapsack - practice greedy choice property
5. Write proofs for each solution

FAQ

Q: Do I need to prove correctness in every interview?

A: For greedy problems at top companies, yes. It shows deep understanding.

Q: Which proof technique should I use?

A: Exchange argument is most common for greedy. Use induction for recursive/state-based problems.

Q: What if I can't prove it?

A: Try to find a counterexample. If greedy fails on a counterexample, use DP instead.

Q: How formal should the proof be?

A: Explain the key insight clearly. Full mathematical rigor not required, but logic must be sound.

Conclusion

Proving greedy correctness is what separates good engineers from great ones.

Four techniques:

1. Exchange argument - swap greedy into optimal
2. Greedy choice property - local optimal → global optimal
3. Induction - base case + inductive step
4. Optimal substructure - optimal contains optimal subproblems

When to use:

• Exchange argument: Interval scheduling, selection problems
• Greedy choice property: Most greedy problems
• Induction: Reachability, state tracking
• Optimal substructure: Verify structure

The template:

1. Define greedy choice
2. Prove it's safe (exchange/greedy choice property)
3. Show optimal substructure
4. Handle edge cases
5. Test with examples

Master these techniques, and you'll prove greedy correctness with confidence. For more examples, see Exchange Argument Explained, Greedy Choice Property, and the complete greedy guide.

Next time an interviewer asks "How do you know it's correct?", you'll have the answer.