322 - Coin Change

Difficulty: Medium | Pattern: Dynamic Programming (Bottom-Up) | Company tags: Google, Amazon, Apple, Microsoft

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints: 1 <= coins.length <= 12; 1 <= coins[i] <= 2^31 - 1; 0 <= amount <= 10^4

Approach: Bottom-Up Dynamic Programming

Key insight: This is an unbounded knapsack problem. Define dp[i] = minimum number of coins needed to make amount i.

Recurrence:

dp[0] = 0  (zero coins needed for amount 0)
dp[i] = min(dp[i - coin] + 1) for all coin in coins where i >= coin

Why DP not greedy? Greedy (always use the largest coin) fails: for coins [1, 3, 4] and amount = 6, greedy gives 4+1+1 = 3 coins, but optimal is 3+3 = 2 coins.

Algorithm:

1. Initialize dp array of size amount + 1 with infinity (unreachable)
2. Set dp[0] = 0
3. For each amount from 1 to amount, try each coin: if coin <= i, update dp[i] = min(dp[i], dp[i - coin] + 1)
4. Return dp[amount] if not infinity, else -1

Solution (Python)

def coinChange(coins: list[int], amount: int) -> int:
    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

Dry Run

coins = [1, 2, 5], amount = 5

i	dp[i]	How?
0	0	base case
1	1	0 + coin(1) → dp[0]+1=1
2	1	min(dp[1]+1=2, dp[0]+1=1) → 1 (coin=2)
3	2	min(dp[2]+1=2, dp[1]+1=2) → 2
4	2	min(dp[3]+1=3, dp[2]+1=2) → 2
5	1	min(dp[4]+1=3, dp[3]+1=3, dp[0]+1=1) → 1 (coin=5)

Result: dp[5] = 1 ✓ (just use a single 5-coin)

Alternative: BFS Approach

Treat this as a shortest-path problem: nodes are amounts 0..amount, edges connect amount i to amount i + coin. BFS from 0 finds the shortest path to amount.

from collections import deque

def coinChange(coins, amount):
    if amount == 0: return 0
    queue = deque([0])
    visited = {0}
    steps = 0
    while queue:
        steps += 1
        for _ in range(len(queue)):
            curr = queue.popleft()
            for coin in coins:
                nxt = curr + coin
                if nxt == amount: return steps
                if nxt < amount and nxt not in visited:
                    visited.add(nxt)
                    queue.append(nxt)
    return -1

Edge Cases

• amount = 0 → return 0 (base case)
• No solution exists (e.g., coins [2], amount 3) → return -1
• Single coin equals amount → return 1
• Very large amount → be careful with initialization (use float('inf'), not amount + 1)

Complexity

• Time: O(amount × len(coins)) — nested loop
• Space: O(amount) — the dp array