Common Greedy Patterns - Learning Module

Loading content...

0/276

Minimum Coins (When Greedy Works)

The Cashier's Algorithm

Every time you receive change at a store, an algorithm runs—whether in a cashier's head or a vending machine's processor. The goal is simple: give the customer the correct change using the fewest coins possible.

Most people solve this instinctively: use the largest coins first. Need to make 78 cents? Use 3 quarters (75¢), then 3 pennies (3¢). Total: 6 coins. This "largest first" approach feels natural, efficient, and obviously correct.

But here's the catch: this greedy approach isn't always optimal. In some currency systems, greedily selecting the largest coin can lead to suboptimal solutions—or even fail to find change when it exists. Understanding when greedy works versus when it fails is crucial for algorithm design.

What You Will Learn

By the end of this page, you will master the greedy coin change algorithm—its formal definition, implementation, correctness conditions, failure cases, and the mathematical properties that distinguish canonical coin systems from non-canonical ones. You'll also understand when to pivot to dynamic programming.

Problem Formalization

The Coin Change Problem (Minimum Coins Variant):

Input:

A set of coin denominations: D = {d₁, d₂, ..., dₖ} where d₁ < d₂ < ... < dₖ
Assume d₁ = 1 (ensures all amounts are achievable)
A target amount: n
Unlimited supply of each denomination

Output:

The minimum number of coins needed to make exactly amount n
Optionally: the actual coins used

Constraints:

Each coin can be used any number of times
The total value must equal exactly n
Minimize the count of coins used

Example with US Currency:

Denominations: {1, 5, 10, 25} (penny, nickel, dime, quarter) Target: 67 cents

Greedy approach:

Use 25¢ (largest ≤ 67): 67 - 25 = 42 remaining
Use 25¢ (largest ≤ 42): 42 - 25 = 17 remaining
Use 10¢ (largest ≤ 17): 17 - 10 = 7 remaining
Use 5¢ (largest ≤ 7): 7 - 5 = 2 remaining
Use 1¢: 2 - 1 = 1 remaining
Use 1¢: 1 - 1 = 0 done

Result: 2 quarters + 1 dime + 1 nickel + 2 pennies = 6 coins

As we'll see, this is indeed optimal for US currency—but proving optimality requires understanding why the greedy choice is "safe."

A Subtle Trap

The coin change problem looks deceptively simple. The greedy solution feels natural and works for familiar currency systems. But this familiarity can blind us to cases where greedy fails catastrophically. Always verify greedy correctness—don't assume it from intuition.

The Greedy Algorithm: Largest First

The greedy approach is elegantly simple:

GREEDY-COIN-CHANGE(denominations[], amount):
    1. Sort denominations in decreasing order
    2. coins_used = empty list
    3. remaining = amount
    
    4. FOR each denomination d in sorted order:
    5.     count = remaining / d  (integer division)
    6.     ADD count coins of denomination d to coins_used
    7.     remaining = remaining - (count × d)
    8.     IF remaining == 0: BREAK
    
    9. IF remaining > 0:
    10.    RETURN "No solution"  // Only if d₁ ≠ 1
    
    11. RETURN coins_used

The Greedy Principle: At each step, use as many of the largest valid denomination as possible before moving to smaller ones.

coin_change_greedy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from typing import List, Tuple, Optional, Dict
 
def greedy_coin_change(
    denominations: List[int], 
    amount: int
) -> Tuple[int, Dict[int, int]]:
    """
    Greedy algorithm for minimum coins.
    
    Args:
        denominations: List of coin values (should include 1 for completeness)
        amount: Target amount to make
        
    Returns:
        Tuple of (total_coins, {denomination: count})
    """
    # Sort in decreasing order
    sorted_denoms = sorted(denominations, reverse=True)
    
    remaining = amount
    coin_count = 0
    coins_used: Dict[int, int] = {}
    
    for denom in sorted_denoms:
        if denom <= remaining:
            # Use as many of this denomination as possible
            count = remaining // denom
            coins_used[denom] = count
            coin_count += count
            remaining -= count * denom
        
        if remaining == 0:
            break
    
    if remaining > 0:
        raise ValueError(f"Cannot make {amount} with given denominations")
    
    return coin_count, coins_used
 
 
def trace_greedy(denominations: List[int], amount: int) -> None:
    """Trace through the greedy algorithm step by step."""
    sorted_denoms = sorted(denominations, reverse=True)
    remaining = amount
    
    print(f"\nMaking change for {amount} with denominations {denominations}")
    print("=" * 60)
    
    total_coins = 0
    for denom in sorted_denoms:
        if denom <= remaining:
            count = remaining // denom
            if count > 0:
                used = count * denom
                remaining -= used
                total_coins += count
                print(f"  Use {count} × {denom:3d} = {used:4d} | Remaining: {remaining:4d}")
    
    print("=" * 60)
    print(f"Total coins used: {total_coins}")
 
 
# Example with US currency
if __name__ == "__main__":
    us_coins = [1, 5, 10, 25]
    trace_greedy(us_coins, 67)
    trace_greedy(us_coins, 30)
    trace_greedy(us_coins, 99)

Time Complexity: O(k) where k is the number of denominations (after a one-time O(k log k) sort)

Space Complexity: O(k) to store the coins used

Why This is Fast:

The greedy algorithm processes each denomination exactly once, performing only division and subtraction—both O(1) operations. Compared to the O(n × k) dynamic programming solution, this is dramatically faster when applicable.

When Greedy Works: Canonical Coin Systems

The greedy algorithm works for some coin systems but not others. A coin system where greedy always produces optimal results is called canonical.

Definition: A coin system D = {d₁, d₂, ..., dₖ} is canonical if the greedy algorithm produces the minimum number of coins for every possible target amount.

Canonical Systems in Practice

Most real-world currency systems are designed to be canonical: US coins {1, 5, 10, 25}, Euro coins {1, 2, 5, 10, 20, 50, 100, 200}, UK coins {1, 2, 5, 10, 20, 50, 100, 200}. This is intentional—canonical systems minimize coin usage in everyday transactions.

Why are these systems canonical?

A sufficient (but not necessary) condition for canonicity is a divisibility chain: each larger denomination is a multiple of all smaller ones.

Example: Powers of 2

Denominations: {1, 2, 4, 8, 16, ...}

This is canonical because:

2 = 2 × 1
4 = 2 × 2
8 = 2 × 4
etc.

When making any amount, using the largest power of 2 that fits is always optimal because you can't do better with smaller coins—you'd need more of them.

Mathematical Insight:

For the divisibility chain case, if dᵢ₊₁ = mᵢ × dᵢ for some multiplier mᵢ, then using mᵢ coins of denomination dᵢ is equivalent to using 1 coin of denomination dᵢ₊₁. The greedy choice of using the larger coin is never worse.

However, not all canonical systems follow this pattern. US currency {1, 5, 10, 25} is canonical despite 25 not being a multiple of 10.

Proof Sketch for US Currency {1, 5, 10, 25}:

We can prove US currency is canonical by case analysis:

An optimal solution uses at most 4 pennies. Proof: 5 pennies = 1 nickel (fewer coins).
An optimal solution uses at most 1 nickel. Proof: 2 nickels = 1 dime (fewer coins).
An optimal solution uses at most 2 dimes. Proof: Not obvious, but:
- 3 dimes (30¢) vs 1 quarter + 1 nickel (30¢): both use 2 coins
- But if you have 3 dimes + 1 nickel (35¢), use 1 quarter + 1 dime: 2 coins vs 4
The greedy algorithm respects all these constraints.

This exhaustive analysis confirms optimality but is tedious. For complex systems, testing or the matrix method is more practical.

When Greedy Fails: Non-Canonical Systems

Understanding failure cases is as important as understanding success. Let's examine concrete examples where the greedy approach produces suboptimal results.

Classic Counterexample

Denominations: {1, 3, 4} Target: 6

Greedy: 4 + 1 + 1 = 3 coins Optimal: 3 + 3 = 2 coins

The greedy algorithm fails by choosing 4 first, forcing two 1s, when two 3s would have been better.

Let's trace through this failure:

greedy_failure_demo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def compare_greedy_vs_optimal(denoms: List[int], amount: int) -> None:
    """Compare greedy solution with brute-force optimal."""
    
    # Greedy solution
    greedy_count, greedy_coins = greedy_coin_change(denoms, amount)
    
    # Dynamic programming for optimal
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    parent = [-1] * (amount + 1)  # Track which coin was used
    
    for i in range(1, amount + 1):
        for coin in denoms:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                parent[i] = coin
    
    # Reconstruct optimal solution
    optimal_coins = {}
    curr = amount
    while curr > 0:
        coin = parent[curr]
        optimal_coins[coin] = optimal_coins.get(coin, 0) + 1
        curr -= coin
    
    print(f"\nDenominations: {denoms}, Target: {amount}")
    print("-" * 50)
    print(f"Greedy:  {greedy_count} coins - {dict(sorted(greedy_coins.items(), reverse=True))}")
    print(f"Optimal: {dp[amount]} coins - {dict(sorted(optimal_coins.items(), reverse=True))}")
    
    if greedy_count > dp[amount]:
        print("⚠️  GREEDY IS SUBOPTIMAL!")
    else:
        print("✓  Greedy matches optimal")
 
 
# Test cases
compare_greedy_vs_optimal([1, 3, 4], 6)   # Greedy fails
compare_greedy_vs_optimal([1, 5, 10, 25], 30)  # Greedy works
compare_greedy_vs_optimal([1, 5, 6, 9], 11)  # Greedy fails

More Failure Examples:

Denominations	Target	Greedy	Optimal	Difference
{1, 3, 4}	6	4+1+1=3	3+3=2	-1 coin
{1, 5, 6, 9}	11	9+1+1=3	6+5=2	-1 coin
{1, 6, 10}	12	10+1+1=3	6+6=2	-1 coin
{1, 7, 10}	14	10+1+1+1+1=5	7+7=2	-3 coins
{1, 15, 25}	30	25+1×5=6	15+15=2	-4 coins

Pattern in Failures:

Greedy fails when a large coin "overshoots" and forces inefficient use of small coins, while a combination of mid-sized coins would have summed exactly. This happens when coins don't have the divisibility properties that ensure greedy safety.

Testing for Canonicity

Given an arbitrary coin system, how do we determine if greedy works? There are several approaches:

Methods to Test Canonicity

•Brute Force Testing: Compare greedy with DP for all amounts up to a certain bound. If they differ anywhere, the system is non-canonical.
•Counterexample Search: Only need to test amounts up to d₁ + dₖ (smallest + largest). If greedy works for this range, it works everywhere.
•Pearson-Mills Theorem: A coin system is canonical iff the greedy solution equals the optimal solution for all amounts from 1 to the sum of two largest denominations.
•Structural Analysis: Check if the system satisfies known sufficient conditions for canonicity.

test_canonicity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def is_canonical(denominations: List[int], verbose: bool = False) -> bool:
    """
    Test if a coin system is canonical by comparing greedy with DP
    for all amounts up to a sufficient bound.
    
    Bound: sum of two largest denominations (sufficient by Pearson-Mills)
    """
    sorted_denoms = sorted(denominations, reverse=True)
    
    # Bound for testing
    if len(sorted_denoms) >= 2:
        test_bound = sorted_denoms[0] + sorted_denoms[1]
    else:
        test_bound = sorted_denoms[0] * 2
    
    for amount in range(1, test_bound + 1):
        greedy_count = greedy_coin_count(denominations, amount)
        optimal_count = dp_coin_count(denominations, amount)
        
        if greedy_count != optimal_count:
            if verbose:
                print(f"Non-canonical at amount {amount}:")
                print(f"  Greedy: {greedy_count} coins")
                print(f"  Optimal: {optimal_count} coins")
            return False
    
    return True
 
def greedy_coin_count(denoms: List[int], amount: int) -> int:
    """Count coins using greedy algorithm."""
    sorted_denoms = sorted(denoms, reverse=True)
    remaining = amount
    count = 0
    
    for d in sorted_denoms:
        count += remaining // d
        remaining %= d
    
    return count
 
def dp_coin_count(denoms: List[int], amount: int) -> int:
    """Count minimum coins using dynamic programming."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in denoms:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    
    return dp[amount] if dp[amount] != float('inf') else -1
 
 
# Test various coin systems
print("Testing coin systems for canonicity:")
print("-" * 50)
print(f"US coins {{1,5,10,25}}: {'Canonical' if is_canonical([1,5,10,25]) else 'Non-canonical'}")
print(f"{{1,3,4}}: {'Canonical' if is_canonical([1,3,4], verbose=True) else 'Non-canonical'}")
print(f"{{1,5,6,9}}: {'Canonical' if is_canonical([1,5,6,9], verbose=True) else 'Non-canonical'}")
print(f"Powers of 2 {{1,2,4,8,16}}: {'Canonical' if is_canonical([1,2,4,8,16]) else 'Non-canonical'}")

Practical Advice

In interviews, if the problem specifies standard currency denominations (US, Euro, etc.), greedy is safe. For arbitrary denominations, either verify canonicity or use dynamic programming. When in doubt, DP is always correct—greedy is an optimization when applicable.

Greedy vs Dynamic Programming

The coin change problem perfectly illustrates the greedy-DP tradeoff:

Algorithm Comparison for Coin Change
Aspect	Greedy	Dynamic Programming
Time Complexity	O(k)	O(n × k)
Space Complexity	O(1) or O(k)	O(n)
Correctness	Only for canonical systems	Always correct
Implementation	Very simple	Moderate complexity
When to Use	Known canonical systems	Unknown or arbitrary denominations

The Dynamic Programming Solution:

For completeness, here's the DP approach that always works:

DP-COIN-CHANGE(denominations[], amount):
    1. dp[0] = 0  // 0 coins needed for amount 0
    2. dp[1..amount] = ∞  // Initialize to infinity
    
    3. FOR i = 1 TO amount:
    4.     FOR each coin in denominations:
    5.         IF coin <= i AND dp[i - coin] + 1 < dp[i]:
    6.             dp[i] = dp[i - coin] + 1
    
    7. RETURN dp[amount]

Recurrence Relation:

dp[i] = min(dp[i - coin] + 1) for all valid coins

This explores all choices and guarantees optimality through the principle of optimal substructure.

coin_change_dp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def min_coins_dp(denominations: List[int], amount: int) -> Tuple[int, List[int]]:
    """
    Dynamic programming solution for minimum coins.
    Works for any coin system, canonical or not.
    
    Returns:
        Tuple of (min_coins, list_of_coins_used)
    """
    if amount == 0:
        return 0, []
    
    # dp[i] = minimum coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    # Track which coin was used to reach each amount
    coin_used = [-1] * (amount + 1)
    
    for i in range(1, amount + 1):
        for coin in denominations:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                coin_used[i] = coin
    
    if dp[amount] == float('inf'):
        raise ValueError(f"Cannot make {amount} with given denominations")
    
    # Reconstruct the solution
    coins = []
    curr = amount
    while curr > 0:
        coins.append(coin_used[curr])
        curr -= coin_used[curr]
    
    return dp[amount], coins
 
 
# Compare both approaches
denoms = [1, 3, 4]
amount = 6
 
greedy_count, greedy_coins = greedy_coin_change(denoms, amount)
dp_count, dp_coins = min_coins_dp(denoms, amount)
 
print(f"Denominations: {denoms}, Amount: {amount}")
print(f"Greedy:  {greedy_count} coins -> {greedy_coins}")
print(f"DP:      {dp_count} coins -> {dp_coins}")

Decision Framework

Use greedy when: (1) denominations are standard currency, (2) you've verified canonicity, or (3) performance is critical and you've tested the specific amounts. Use DP when: (1) denominations are arbitrary, (2) correctness is paramount, or (3) you're unsure about the system's properties.

Real-World Applications

The coin change problem extends far beyond actual currency:

Applications Beyond Currency

•Vending Machine Design: Optimize coin dispensers by analyzing which denominations minimize total coins dispensed across typical transactions.
•Network Packet Sizing: Minimize the number of packets to transmit data when packet sizes are fixed options (MTU considerations).
•Resource Allocation: Assign servers with fixed capacity options to workloads—minimize total servers used.
•Stamp Collecting: The 'postage stamp problem'—minimize stamps needed for any postage amount (classic combinatorics problem).
•Change-Making Machines: ATMs and self-checkout optimize bill dispensing using similar logic.
•Bandwidth Allocation: Allocating fixed bandwidth slices to minimize waste.

Currency Design Insight:

The fact that most world currencies are canonical is not accidental. When designing a currency system, central banks and economists optimize for:

Minimizing coins in transactions (user convenience)
Minimizing coins to carry (wallet size)
Production cost considerations (fewer coin types = cheaper)
Historical and psychological factors (familiar values)

The US quarter (25 cents) instead of 20 cents is interesting—it's less "mathematically clean" but has historical roots and conveniently divides a dollar into fourths.

Some proposed "optimal" denomination systems (like {1, 5, 18, 25, 45, 100} for minimizing average coins) are mathematically superior but impractical due to unfamiliar values.

Interview Perspective

Coin change is an interview classic—but the greedy-vs-DP distinction is what separates good from great answers.

Strong Candidate Response

•Asks about denominations first
•Mentions greedy works for canonical systems
•Explains when greedy fails with example
•Offers DP as general solution
•Discusses time/space tradeoffs

Weak Candidate Response

•Jumps straight to one solution
•Claims greedy always works
•Can't explain failure cases
•Doesn't know DP approach
•No complexity analysis

Interview Script

"For coin change, the approach depends on the denominations. If they're standard currency like US coins, greedy works: always take the largest coin that fits. But for arbitrary denominations like {1, 3, 4}, greedy can fail—making 6 with greedy gives 4+1+1 (3 coins) but 3+3 (2 coins) is better. For general denominatons, I'd use DP: dp[i] = min(dp[i-coin]+1) for each coin, giving O(n×k) time."

Summary: The Minimum Coins Pattern

Key Takeaways

•Greedy Approach: Use largest denomination first, repeat until done. Time: O(k), elegant and fast.
•Works Only for Canonical Systems: Standard currencies (US, Euro) are designed to be canonical. Arbitrary denominations may not be.
•Classic Failure: {1, 3, 4} making 6 → greedy gives 3 coins (4+1+1), optimal is 2 coins (3+3).
•DP Always Works: O(n × k) solution handles any denomination set correctly.
•Testing Canonicity: Check greedy vs DP for amounts up to sum of two largest denominations.
•Interview Strategy: Always clarify denominations. Explain greedy limitations. Have DP ready.

The Deeper Lesson:

Coin change teaches a crucial meta-lesson: greedy algorithms require proof of correctness. The temptation to assume greedy works because it feels right leads to subtle bugs. "Largest first" is intuitive—but intuition fails for {1, 3, 4}.

This pattern appears whenever you're making sequential choices from a set of options: should you be greedy (fast, simple) or exhaustive (correct, slower)? The answer depends on the problem structure—and recognizing that structure is the skill we're building.

Page Complete

You now understand the coin change problem from both greedy and dynamic programming perspectives, including when each approach is appropriate. Next, we'll explore the gas station problem—another beloved greedy pattern with elegant circular reasoning.