Coin Change

Problem Statement

You are given an array of distinct coin denominations coins and an integer amount. Return the minimum number of coins needed to make up amount. If impossible, return -1. You have an unlimited supply of each 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

Difficulty: Medium

---

Pattern Recognition

• What is the structure of the input? A set of coin values and a target amount.
• What are we optimizing? Minimum number of coins summing to amount.
• What pattern does this suggest? Dynamic programming — unbounded knapsack variant (each coin can be used infinitely).
• Why does this pattern fit? The minimum-coin count for any amount i depends only on minimum counts for smaller amounts (i - c for each coin c). Optimal substructure + overlapping subproblems = DP.

---

Approach

Brute Force — Recursion

For each coin, recurse into amount - coin and take the minimum.

dfs(amount):
  if amount < 0: return infinity
  if amount == 0: return 0
  return 1 + min(dfs(amount - c) for c in coins)

Time: O(C^amount) — exponential branching. Space: O(amount) stack depth. Why insufficient: 10^4 amount with 12 coins is wildly too slow.

Memoized Recursion (Top-Down DP)

Same recurrence, cache results. O(amount * coins) time.

Optimal — Bottom-Up DP

Key Insight: Build dp[i] = minimum coins to make amount i, starting from dp[0] = 0 and computing upward. For each i, try every coin: dp[i] = 1 + min(dp[i - c]).

Step-by-step:

1. dp = array of size amount+1, filled with infinity.
2. dp[0] = 0 (zero coins make zero).
3. For i = 1..amount, for each coin c: if i - c >= 0, dp[i] = min(dp[i], dp[i - c] + 1).
4. Return dp[amount] (or -1 if it's still infinity).

Time: O(amount * coins). Space: O(amount).

---

Walkthrough

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

i	dp[i] computation	dp[i]
0	base	0
1	dp[0]+1 (via coin 1)	1
2	min(dp[1]+1, dp[0]+1)	1
3	min(dp[2]+1, dp[1]+1)	2
4	min(dp[3]+1, dp[2]+1)	2
5	min(dp[4]+1, dp[3]+1, dp[0]+1)	1
6	min(dp[5]+1, dp[4]+1, dp[1]+1)	2
7	min(dp[6]+1, dp[5]+1, dp[2]+1)	2
8	min(dp[7]+1, dp[6]+1, dp[3]+1)	3
9	min(dp[8]+1, dp[7]+1, dp[4]+1)	3
10	min(dp[9]+1, dp[8]+1, dp[5]+1)	2
11	min(dp[10]+1, dp[9]+1, dp[6]+1)	3

Answer: 3 (e.g., 5+5+1).

---

Implementation

TypeScript

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (i - c >= 0 && dp[i - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i)
            for (int c : coins)
                if (i - c >= 0 && dp[i-c] != INT_MAX)
                    dp[i] = min(dp[i], dp[i-c] + 1);
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

Watch out: Integer overflow. In C++, if dp[i-c] == INT_MAX, adding 1 overflows to INT_MIN. Guard with an explicit check.

Watch out: Greedy doesn't work. For coins = [1, 3, 4], amount = 6, greedy gives 4 + 1 + 1 = 3, but optimal is 3 + 3 = 2. Always DP.

Watch out: amount = 0 should return 0. The initial dp[0] = 0 and the check for Infinity handles this cleanly.

---

Complexity Analysis

	Time	Space
Brute Force Recursion	O(C^amount)	O(amount)
Memoized DP	O(amount * coins)	O(amount)
Bottom-Up DP	O(amount * coins)	O(amount)

Bottleneck: Every (i, coin) pair is evaluated once.

---

Edge Cases

1. amount = 0 — Return 0 immediately via dp[0].
2. No coin divides amount cleanly — Return -1 via the Infinity check.
3. Single coin = amount — Return 1.
4. Coin larger than amount — Skip in the inner loop (the bounds check i - c >= 0).
5. Multiple same-denomination coins — The problem says distinct; no issue.

---

Related Problems

• LC 518 — Coin Change II: Count the number of ways, not min. Similar DP structure.
• LC 377 — Combination Sum IV: Count ordered sequences. Swap the loop order to count permutations.
• LC 279 — Perfect Squares: dp[n] = min number of squares. Special case of Coin Change with square coins.
• LC 983 — Minimum Cost For Tickets: Unbounded-like DP with time-based transitions.

---

What Is Expected at Each Level?

Junior / New Grad: Recognize DP. Might write recursive with memoization first. Reach O(amount * coins) with guidance.

Mid-level: Immediately write bottom-up DP. Discuss the greedy counterexample proactively.

Senior: Compare top-down vs bottom-up, reason about constant-factor speedups (sort coins descending, early prune in recursion), and extend to return the coin set used (parent pointer). Discuss BFS as an alternative (shortest-path framing where nodes = amounts).