You're in an interview. The problem says: "Find the minimum number of coins to make change for amount n."
You've seen this pattern before. You write a greedy solution:
def coinChange(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count if amount == 0 else -1You submit. Wrong Answer.
The input was coins = [1, 3, 4], amount = 6. Your greedy solution returned 3 coins [4, 1, 1]. The optimal answer is 2 coins [3, 3].
What went wrong? You used greedy when you needed dynamic programming. This is the #1 algorithm interview mistake, and it costs more interviews than any other pattern confusion.
In this guide, you'll learn when greedy works vs when DP is required, systematic decision frameworks, how to test with counterexamples, and how to avoid this trap forever.
Use Greedy when:
Use DP when:
Decision rule: Always test greedy with counterexamples. If one exists, use DP.
Definition: Make the best immediate choice at each step, never reconsidering.
Key insight: The locally optimal choice is also globally optimal.
Example (Interval Scheduling):
Intervals: [(1,4), (3,5), (0,6), (5,7)]
Greedy choice: Pick interval ending earliest
Step 1: Pick (1,4) - ends at 4
Step 2: Pick (5,7) - ends at 7, starts after 4
Result: 2 intervals (optimal) ✓
Why it works: Picking earliest-ending interval leaves maximum room
for future intervals. This greedy choice is provably optimal.Definition: Build up solutions from smaller subproblems, considering all choices at each step.
Key insight: Optimal solution depends on optimal solutions to overlapping subproblems.
Example (Coin Change):
Coins: [1, 3, 4], Amount: 6
DP approach: Try all coins at each step
dp[0] = 0
dp[1] = 1 (use coin 1)
dp[2] = 2 (use coin 1 twice)
dp[3] = 1 (use coin 3)
dp[4] = 1 (use coin 4)
dp[5] = 2 (dp[4] + coin 1 or dp[2] + coin 3)
dp[6] = 2 (dp[3] + coin 3) ← optimal: [3, 3]
Result: 2 coins (optimal) ✓
Why greedy fails: Greedy picks 4 first (largest), then forced to use
[4,1,1]=3 coins. DP explores all choices and finds [3,3]=2 coins.| Aspect | Greedy | Dynamic Programming |
|---|---|---|
| Decision | Make best immediate choice | Explore all choices |
| Reconsideration | Never | Always (via subproblems) |
| Subproblems | Solve one subproblem | Solve all subproblems |
| Correctness | Must prove | Guaranteed if recurrence correct |
| Time Complexity | Usually O(n) or O(n log n) | Usually O(n²) or O(n × m) |
| Space Complexity | Usually O(1) | Usually O(n) or O(n × m) |
| When it works | Greedy choice property holds | Optimal substructure + overlapping subproblems |
Use this systematic approach to decide between greedy and DP:
Question: Does the problem ask for minimum, maximum, or optimal?
YES → Continue to Step 2
NO → Greedy/DP probably not applicableExamples:
Question: Is there an obvious "best" choice at each step?
YES → Continue to Step 3
NO → Likely need DPExamples:
Question: Can you find an input where greedy gives wrong answer?
YES (found counterexample) → Use DP
NO (no counterexample found) → Continue to Step 4Critical counterexamples:
Coin Change:
coins = [1, 3, 4], amount = 6
Greedy: [4, 1, 1] = 3 coins
Optimal: [3, 3] = 2 coins
Greedy FAILS ✗0/1 Knapsack:
weights = [10, 20, 30], values = [60, 100, 120], capacity = 50
Greedy (by value/weight): Pick item 1 (ratio=6), item 2 (ratio=5)
Total: weight=30, value=160
Optimal: Pick item 2 and item 3
Total: weight=50, value=220
Greedy FAILS ✗Question: Can you prove greedy choice property holds?
YES → Greedy is correct ✓
NO → Use DP (safer)Proof techniques:
See detailed guide: Greedy Proof Techniques
Optimization problem?
|
v
Can identify greedy choice?
/ \
YES NO
| |
v v
Counterexample? Use DP
/ \
YES NO
| |
v v
Use DP Can prove?
/ \
YES NO
| |
v v
Greedy Use DP
(safer)Problem: Maximize number of non-overlapping intervals.
Greedy choice: Pick interval ending earliest.
Why it works:
def maxIntervals(intervals):
intervals.sort(key=lambda x: x[1]) # Sort by end time
count = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
count += 1
last_end = end
return count
# Example
intervals = [(1,3), (2,5), (4,7), (6,9)]
print(maxIntervals(intervals)) # 2: [(1,3), (4,7)]Proof (Exchange Argument):
Time: O(n log n), Space: O(1)
See detailed guide: Interval Scheduling Template
Problem: Maximize value in knapsack (can take fractions of items).
Greedy choice: Pick items by highest value/weight ratio.
Why it works:
def fractionalKnapsack(values, weights, capacity):
# Calculate value/weight ratios
items = [(v/w, w, v) for v, w in zip(values, weights)]
items.sort(reverse=True) # Highest ratio first
total_value = 0
for ratio, weight, value in items:
if capacity >= weight:
# Take entire item
total_value += value
capacity -= weight
else:
# Take fraction
total_value += ratio * capacity
break
return total_value
# Example
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractionalKnapsack(values, weights, capacity)) # 240
# Take all of item 3 (120), all of item 2 (100), 2/3 of item 1 (20)Proof: Taking highest ratio first maximizes value per unit weight. Since we can take fractions, this is always optimal.
Time: O(n log n), Space: O(n)
Problem: Determine if you can reach the last index.
Greedy choice: Track maximum reachable position.
Why it works:
def canJump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return True
# Example
print(canJump([2,3,1,1,4])) # True
print(canJump([3,2,1,0,4])) # FalseProof: If we can't reach position i with maximum possible reach from 0..i-1, we can never reach i (or anything beyond).
Time: O(n), Space: O(1)
See detailed guide: Jump Game: Greedy vs DP
Problem: Minimum coins to make change for amount n.
Why greedy fails:
# WRONG: Greedy approach
def coinChangeGreedy(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# Counterexample
coins = [1, 3, 4]
amount = 6
# Greedy: Pick 4 (largest), then 1, 1 → [4,1,1] = 3 coins
print(coinChangeGreedy(coins, amount)) # 3 (WRONG)
# Optimal: [3, 3] = 2 coins ✗Correct DP solution:
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Example
print(coinChange([1, 3, 4], 6)) # 2: [3, 3] ✓Why DP is needed: Greedy choice (largest coin) doesn't guarantee global optimum. Must explore all choices.
Time: O(amount × coins), Space: O(amount)
See detailed guide: Why Greedy Fails on Coin Change
Problem: Maximize value in knapsack (can't take fractions).
Why greedy fails:
# WRONG: Greedy by value/weight ratio
def knapsackGreedy(values, weights, capacity):
items = [(v/w, w, v, i) for i, (v, w) in enumerate(zip(values, weights))]
items.sort(reverse=True)
total_value = 0
for ratio, weight, value, idx in items:
if capacity >= weight:
total_value += value
capacity -= weight
return total_value
# Counterexample
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
# Greedy: Pick item 0 (ratio=6), item 1 (ratio=5)
# weight=30, value=160
print(knapsackGreedy(values, weights, capacity)) # 160 (WRONG)
# Optimal: Pick item 1 and item 2
# weight=50, value=220 ✗Correct DP solution:
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Don't take item i-1
dp[i][w] = dp[i-1][w]
# Take item i-1 if it fits
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# Example
print(knapsack([60, 100, 120], [10, 20, 30], 50)) # 220 ✓Why DP is needed: Can't take fractions, so greedy by ratio fails. Must explore all combinations.
Time: O(n × capacity), Space: O(n × capacity)
Problem: Find length of longest increasing subsequence.
Why greedy fails:
# WRONG: Greedy approach (pick smallest next element)
def lisGreedy(nums):
if not nums:
return 0
length = 1
last = nums[0]
for num in nums[1:]:
if num > last:
length += 1
last = num
return length
# Counterexample
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# Greedy: [10, 101] = length 2 (picks 10, then 101)
print(lisGreedy(nums)) # 2 (WRONG)
# Optimal: [2, 3, 7, 101] or [2, 5, 7, 101] = length 4 ✗Correct DP solution:
def lengthOfLIS(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# Example
print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 4 ✓Why DP is needed: Greedy choice of smallest next element misses longer subsequences. Must explore all possibilities.
Time: O(n²), Space: O(n)
Always test greedy with these classic counterexamples:
coins = [1, 3, 4], amount = 6
# Greedy: [4, 1, 1] = 3
# Optimal: [3, 3] = 2
# Verdict: Greedy FAILS ✗values = [60, 100, 120], weights = [10, 20, 30], capacity = 50
# Greedy (ratio): items 0,1 → value=160
# Optimal: items 1,2 → value=220
# Verdict: Greedy FAILS ✗intervals = [(1,3), (2,5), (4,7)]
# Greedy (end time): [(1,3), (4,7)] = 2
# Optimal: same = 2
# Verdict: Greedy WORKS ✓nums = [2, 3, 1, 1, 4]
# Greedy (max reach): reach=8 ≥ 4 → True
# Optimal: same → True
# Verdict: Greedy WORKS ✓Sometimes you can combine greedy and DP:
def hybridApproach(problem):
# Try greedy first (fast)
greedy_result = greedySolution(problem)
# Verify with DP (slow but correct)
if needsVerification:
dp_result = dpSolution(problem)
return dp_result
return greedy_resultdef greedyThenDP(items):
# Greedy: Sort to enable DP optimization
items.sort(key=lambda x: x.value)
# DP: Solve on sorted items
return dpSolution(items)❌ Wrong:
# "It's an optimization problem, so greedy should work"
def solve(problem):
return greedySolution(problem) # No proof!✅ Correct:
# Always test with counterexamples first
def solve(problem):
# Test: Does greedy fail on known counterexamples?
if hasCounterexample(problem):
return dpSolution(problem)
return greedySolution(problem)❌ Wrong:
# Only test on simple inputs
coins = [1, 2, 5], amount = 11
# Greedy works here, so assume it always works✅ Correct:
# Test on adversarial inputs
coins = [1, 3, 4], amount = 6
# Greedy fails here, so use DP❌ Wrong:
# Using O(n²) DP for interval scheduling
def maxIntervals(intervals):
# Complex DP solution...
# Time: O(n²), Space: O(n)✅ Correct:
# Using O(n log n) greedy
def maxIntervals(intervals):
intervals.sort(key=lambda x: x[1])
# Simple greedy solution...
# Time: O(n log n), Space: O(1)| Problem | Greedy Works? | Why? |
|---|---|---|
| Interval Scheduling | ✅ Yes | Earliest end time is provably optimal |
| Fractional Knapsack | ✅ Yes | Can take fractions, ratio is optimal |
| Jump Game | ✅ Yes | Max reach is sufficient |
| Gas Station | ✅ Yes | Can't reach from i→j means can't from any i'→j |
| Activity Selection | ✅ Yes | Same as interval scheduling |
| Coin Change (arbitrary) | ❌ No | Counterexample: [1,3,4], amount=6 |
| 0/1 Knapsack | ❌ No | Can't take fractions, ratio fails |
| Longest Increasing Subsequence | ❌ No | Greedy misses longer subsequences |
| Edit Distance | ❌ No | No greedy choice property |
| Partition Equal Subset Sum | ❌ No | NP-complete, need DP |
To master the greedy vs DP distinction:
Q: How do I know if greedy choice property holds?
A: Try to find a counterexample. If you can't, try to prove it with exchange argument or induction. See Greedy Proof Techniques.
Q: Can I always use DP instead of greedy?
A: Yes, DP is more general, but greedy is faster when it works. Greedy is O(n) or O(n log n), DP is often O(n²) or worse.
Q: What if I'm not sure in an interview?
A: State both approaches: "Greedy might work if [condition], but to be safe, I'll use DP which is guaranteed correct." Then implement DP.
Q: Are there problems where both work?
A: Yes! Jump Game can be solved with both greedy (O(n)) and DP (O(n²)). Greedy is better when it works.
The greedy vs DP distinction is the most important decision in algorithm interviews.
Key principles:
The decision framework:
When greedy works:
When you need DP:
Master this distinction, and you'll never submit a wrong greedy solution again. For specific patterns, see the complete greedy guide, Interval Scheduling Template, and Why Greedy Fails on Coin Change.
Next time you see an optimization problem, ask: "Does greedy choice property hold?" Test it. Prove it. Or use DP.
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