You're solving Coin Change. The problem seems perfect for greedy: "Find minimum coins to make change." You write:
def coinChange(coins, amount):
coins.sort(reverse=True) # Largest first
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count if amount == 0 else -1You test with US coins [1, 5, 10, 25] and amount 41. It works! Returns 4 coins: [25, 10, 5, 1]. ✓
Then you submit to LeetCode. Wrong Answer.
The test case: coins = [1, 3, 4], amount = 6.
Your greedy: [4, 1, 1] = 3 coins.
Optimal: [3, 3] = 2 coins. ✗
What went wrong? Greedy works for US coins but fails for arbitrary coin systems. This is the #1 greedy counterexample in algorithm interviews, and understanding why it fails is crucial.
Greedy fails on Coin Change because:
[1, 3, 4], amount 6 → greedy gives 3, optimal is 2Use DP instead:
Decision rule: Greedy works for canonical coin systems (US coins). For arbitrary coins, use DP.
def coinChangeGreedy(coins, amount):
"""
WRONG: Greedy approach for arbitrary coin systems.
Works for US coins, fails for arbitrary coins.
"""
coins.sort(reverse=True) # Largest first
count = 0
for coin in coins:
# Take as many of this coin as possible
num_coins = amount // coin
count += num_coins
amount -= num_coins * coin
return count if amount == 0 else -1coins = [1, 5, 10, 25]
amount = 41
# Greedy:
# 41 ÷ 25 = 1 coin (25), remaining = 16
# 16 ÷ 10 = 1 coin (10), remaining = 6
# 6 ÷ 5 = 1 coin (5), remaining = 1
# 1 ÷ 1 = 1 coin (1), remaining = 0
# Result: [25, 10, 5, 1] = 4 coins ✓
print(coinChangeGreedy([1, 5, 10, 25], 41)) # 4 (correct)Why it works for US coins: US coin system is canonical—greedy always gives optimal solution.
coins = [1, 3, 4]
amount = 6
# Greedy:
# 6 ÷ 4 = 1 coin (4), remaining = 2
# 2 ÷ 3 = 0 coins, remaining = 2
# 2 ÷ 1 = 2 coins (1,1), remaining = 0
# Result: [4, 1, 1] = 3 coins ✗
# Optimal:
# 6 ÷ 3 = 2 coins (3, 3)
# Result: [3, 3] = 2 coins ✓
print(coinChangeGreedy([1, 3, 4], 6)) # 3 (WRONG)
# Optimal is 2Why it fails: Picking the largest coin (4) forces us into a suboptimal path.
Input: coins = [1, 3, 4], amount = 6
Greedy decision tree:
Amount: 6
├─ Take 4 (largest): remaining = 2
│ ├─ Take 3: can't (3 > 2)
│ └─ Take 1: remaining = 1
│ └─ Take 1: remaining = 0
│ Result: [4, 1, 1] = 3 coins ✗Optimal decision tree:
Amount: 6
├─ Take 3: remaining = 3
│ └─ Take 3: remaining = 0
│ Result: [3, 3] = 2 coins ✓The problem: Greedy picks 4 (largest), which looks good locally but leads to suboptimal global solution.
Example 2:
coins = [1, 5, 6, 9]
amount = 11
# Greedy: [9, 1, 1] = 3 coins ✗
# Optimal: [5, 6] = 2 coins ✓Example 3:
coins = [1, 7, 10]
amount = 14
# Greedy: [10, 1, 1, 1, 1] = 5 coins ✗
# Optimal: [7, 7] = 2 coins ✓Pattern: Greedy fails when largest coin creates a "bad" remainder that requires many small coins.
Definition: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
For Coin Change: "Taking the largest coin first is always part of an optimal solution."
Counterexample:
coins = [1, 3, 4], amount = 6
Claim: Taking 4 (largest) is optimal
Proof by contradiction:
If we take 4, remaining = 2
Best we can do: [4, 1, 1] = 3 coins
But optimal solution is [3, 3] = 2 coins
Optimal solution does NOT include coin 4
Therefore, greedy choice property is VIOLATED ✗US coins: [1, 5, 10, 25]
Property: Each coin is ≥ 2× the previous coin (approximately).
Result: Taking largest coin never creates a remainder that requires more coins than not taking it.
Proof sketch: If you can make amount n with k coins without using the largest coin c, you can make it with ≤ k coins using c (because c ≥ 2× next largest).
Canonical systems: Greedy works for [1, 5, 10, 25], [1, 2, 5, 10, 20, 50], etc.
Non-canonical systems: Greedy fails for [1, 3, 4], [1, 5, 6, 9], etc.
def coinChange(coins: List[int], amount: int) -> int:
"""
Find minimum coins to make change using DP.
Args:
coins: Available coin denominations
amount: Target amount
Returns:
Minimum number of coins, or -1 if impossible
Time: O(amount × len(coins))
Space: O(amount)
"""
# dp[i] = minimum coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins for amount 0
# Build up solutions for all amounts
for i in range(1, amount + 1):
# Try each coin
for coin in coins:
if coin <= i:
# Take coin, add to solution for (i - coin)
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Examples
print(coinChange([1, 3, 4], 6)) # 2: [3, 3]
print(coinChange([1, 5, 6, 9], 11)) # 2: [5, 6]
print(coinChange([2], 3)) # -1: impossibleKey insight: DP explores all choices at each step, not just the greedy choice.
Recurrence relation:
dp[i] = min(dp[i - coin] + 1) for all coins ≤ iExample trace: coins = [1, 3, 4], amount = 6
dp[0] = 0
dp[1] = min(dp[1-1] + 1) = dp[0] + 1 = 1
(use coin 1)
dp[2] = min(dp[2-1] + 1) = dp[1] + 1 = 2
(use coin 1 twice)
dp[3] = min(dp[3-1] + 1, dp[3-3] + 1)
= min(dp[2] + 1, dp[0] + 1)
= min(3, 1) = 1
(use coin 3 once)
dp[4] = min(dp[4-1] + 1, dp[4-3] + 1, dp[4-4] + 1)
= min(dp[3] + 1, dp[1] + 1, dp[0] + 1)
= min(2, 2, 1) = 1
(use coin 4 once)
dp[5] = min(dp[5-1] + 1, dp[5-3] + 1, dp[5-4] + 1)
= min(dp[4] + 1, dp[2] + 1, dp[1] + 1)
= min(2, 3, 2) = 2
(use coins 4+1 or 3+1+1)
dp[6] = min(dp[6-1] + 1, dp[6-3] + 1, dp[6-4] + 1)
= min(dp[5] + 1, dp[3] + 1, dp[2] + 1)
= min(3, 2, 3) = 2
(use coins 3+3) ✓
Result: 2 coins (optimal)| Aspect | Greedy | DP |
|---|---|---|
| Approach | Take largest coin first | Try all coins |
| Time | O(n) | O(amount × coins) |
| Space | O(1) | O(amount) |
| Correctness | Only for canonical systems | Always correct |
| When to use | US coins, canonical systems | Arbitrary coin systems |
Question 1: Is the coin system canonical (like US coins)?
├─ YES → Greedy works ✓
└─ NO → Continue to Question 2
Question 2: Can you find a counterexample?
├─ YES (found counterexample) → Use DP ✓
└─ NO (no counterexample) → Test more, or use DP to be safe
Question 3: Is performance critical?
├─ YES and coins are canonical → Use greedy
└─ Otherwise → Use DP (safer)Quick test: Try these amounts with your coin system:
def test_greedy_vs_dp(coins):
"""Test if greedy matches DP for small amounts."""
for amount in range(1, 100):
greedy_result = coinChangeGreedy(coins, amount)
dp_result = coinChange(coins, amount)
if greedy_result != dp_result:
print(f"Counterexample: amount={amount}")
print(f" Greedy: {greedy_result}")
print(f" DP: {dp_result}")
return False
return True
# Test
print(test_greedy_vs_dp([1, 3, 4])) # Finds counterexample at amount=6
print(test_greedy_vs_dp([1, 5, 10, 25])) # No counterexample (canonical)❌ Wrong:
# "It's a coin problem, so greedy should work"
def coinChange(coins, amount):
return coinChangeGreedy(coins, amount) # WRONG for arbitrary coins✅ Correct:
# Always use DP for arbitrary coin systems
def coinChange(coins, amount):
return coinChangeDp(coins, amount) # Correct for all systems❌ Wrong:
# Only test with US coins
coins = [1, 5, 10, 25]
# Greedy works, assume it always works✅ Correct:
# Test with non-canonical systems
test_cases = [
([1, 3, 4], 6), # Counterexample
([1, 5, 6, 9], 11), # Counterexample
([1, 7, 10], 14), # Counterexample
]❌ Wrong:
# "Greedy seems to work, let me code it"
# (submits greedy solution without proof)✅ Correct:
# "Let me check if greedy choice property holds"
# "I found a counterexample, so I'll use DP"To master the greedy vs DP distinction:
[1, 3, 4], amount 6Q: Why does greedy work for US coins?
A: US coins form a canonical system where each coin is ≥ 2× the previous. This ensures greedy choice property holds.
Q: Can I use greedy for any coin system?
A: Only for canonical systems. For arbitrary coins, use DP.
Q: How do I know if a coin system is canonical?
A: Test with small amounts. If greedy matches DP for all amounts up to 100, it's likely canonical.
Q: Is there a faster algorithm than DP?
A: For arbitrary coins, DP is optimal (O(amount × coins)). For canonical systems, greedy is O(coins).
Coin Change is the classic counterexample that breaks greedy algorithms.
Key takeaways:
[1, 3, 4], amount 6 → greedy gives 3, optimal is 2The lesson:
Master this distinction, and you'll never submit a wrong greedy solution again. For more on greedy vs DP, see Greedy vs Dynamic Programming and the complete greedy guide.
Next time you see Coin Change, reach for DP—not greedy.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free