Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Coin Change (LC 322)

Problem Statement

You are given an array of coin denominations coins and a target amount. Return the fewest number of coins that sum to 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

• Input structure: small coin set, target amount.
• What are we optimizing? minimum count of coins summing to amount.
• Pattern: unbounded knapsack / DP on amount.
• Why: subproblem dp[a] = fewest coins to make a only depends on dp[a - c] for each coin c. Overlapping subproblems, optimal substructure, classic bottom-up DP.

Greedy (always pick the largest coin ≤ remaining) fails in general — try coins = [1, 3, 4], amount = 6. Greedy gives 4+1+1 = 3 coins; DP gives 3+3 = 2. Name this counterexample when your interviewer suggests greedy.

---

Approach

Brute Force — Recursion

Try every coin at every step, recurse on amount - coin. O(amount^n) worst case, times out immediately for amount = 10^4.

Optimal — Bottom-Up DP

Key Insight: dp[a] = 1 + min(dp[a - c]) over all coins c ≤ a. Sentinel dp[a] = amount + 1 means "unreachable" — any true answer is at most amount.

Steps:

1. Create dp of size amount + 1, fill with amount + 1 as a sentinel "infinity".
2. dp[0] = 0.
3. For each a from 1 to amount, for each coin c: if c <= a, dp[a] = min(dp[a], dp[a - c] + 1).
4. Return dp[amount] > amount ? -1 : dp[amount].

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

Alternative — BFS

Treat amounts 0..amount as nodes; edges from a to a - c for each coin c <= a. BFS from amount to 0 gives the fewest steps = fewest coins. Same asymptotic complexity, more constant overhead, sometimes clearer to present.

---

Walkthrough

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

Initialize dp = [0, INF, INF, ...] (size 12).

a	Tried coins	dp[a]
1	1 (dp[0]+1)	1
2	1 (dp[1]+1=2), 2 (dp[0]+1=1)	1
3	1 (dp[2]+1=2), 2 (dp[1]+1=2)	2
4	1 (dp[3]+1=3), 2 (dp[2]+1=2)	2
5	1 (dp[4]+1=3), 2 (dp[3]+1=3), 5 (dp[0]+1=1)	1
6	1 (dp[5]+1=2), 2 (dp[4]+1=3), 5 (dp[1]+1=2)	2
7	1 (dp[6]+1=3), 2 (dp[5]+1=2), 5 (dp[2]+1=2)	2
8	1 (dp[7]+1=3), 2 (dp[6]+1=3), 5 (dp[3]+1=3)	3
9	1, 2, 5 → best 3	3
10	5 (dp[5]+1=2)	2
11	1 (dp[10]+1=3), 2 (dp[9]+1=4), 5 (dp[6]+1=3)	3

Return 3.

---

Implementation

TypeScript

function coinChange(coins: number[], amount: number): number {
    const dp: number[] = new Array(amount + 1).fill(amount + 1); // sentinel = "infinity"
    dp[0] = 0;
    for (let a = 1; a <= amount; a++) {
        for (const coin of coins) {
            if (coin <= a) {
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

C++

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a) {
                dp[a] = min(dp[a], dp[a - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Watch out:

1. Using INT_MAX as the sentinel then doing dp[a - coin] + 1 overflows. amount + 1 is a safe sentinel.
2. Iterating coins in the outer loop instead of the inner is fine for this problem, but for Coin Change II (counting combinations), the loop order matters — that problem requires coins outer, amount inner.
3. Trying to solve with greedy (descending sort + pick largest) is wrong for general coin sets — always confirm with coins = [1,3,4], amount=6.

---

Complexity Analysis

	Time	Space
Brute recursion	O(coins^amount)	O(amount) stack
Memoized DFS	O(amount * coins)	O(amount)
Bottom-Up DP	O(amount * coins)	O(amount)
BFS	O(amount * coins)	O(amount)

Bottleneck: you visit each (amount, coin) pair at least once — O(amount * coins) is optimal within this model.

---

Edge Cases

1. amount = 0 — return 0. dp[0] is already seeded.
2. No combination sums to amount — sentinel stays, return -1.
3. Single coin larger than amount — dp[amount] stays at sentinel, return -1.
4. Coin value 0 (not allowed per constraints, but good to mention) — would cause infinite "improvement" loop; guard if generalizing.
5. Huge coin values (up to INT_MAX) — guard coin <= a prevents negative indexing.
6. amount equals a single coin's value — answer is 1. The DP finds this immediately.

---

Related Problems

• LC 518 — Coin Change II — Count the number of combinations, not the min count. Loop order flips (coins outer).
• LC 377 — Combination Sum IV — Order matters — treat as permutations; amount outer, coins inner.
• LC 983 — Minimum Cost For Tickets — Coin-change flavor with three "coins" (1/7/30 day passes).
• LC 279 — Perfect Squares — Special-case coin change where coins are perfect squares.

---

What Is Expected at Each Level

Junior: Write the recursion first, convert to memoization with guidance, arrive at the bottom-up DP. Explain why greedy fails.

Mid-level: Write bottom-up DP from scratch with the correct sentinel, handle amount = 0 and the impossibility case without prompting.

Senior (L4 target): Contrast Coin Change I vs II vs Combination Sum IV — same-looking problems that need different loop orders. Discuss the BFS equivalence, note it as shortest-path on a DAG, and mention that for very large amounts with small coin count, a generating-function / Frobenius-number argument gives closed-form answers.