#322 Coin Change
frequently reported atPayPalIntuitByteDance / TikTokWalmartAmazonBloomberg
the problem
In plain words
Given coin values and an amount, return the fewest coins that add up to the amount (unlimited coins of each value), or −1 if impossible.
in coins = [1,2,5], amount = 11
out 3
5 + 5 + 1.
in coins = [2], amount = 3
out -1
in coins = [1], amount = 0
out 0
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ − 1
- 0 ≤ amount ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternUnbounded knapsack
Whatever the best answer is, it has a last coin c. Then the rest is the best answer for amount − c. Try every c.
solutions
From brute force to optimal
fewest(a) = 1 + min over coins c ≤ a of fewest(a − c).
- fewest(0) = 0.
- Try each coin, skip impossible sub-results (INF).
k branches per level, depth up to A/m (m = smallest coin) — exponential.
Recursion depth.
class Solution { private static final int INF = Integer.MAX_VALUE; // "impossible" public int coinChange(int[] coins, int amount) { int best = fewest(coins, amount); return best == INF ? -1 : best; } /** Fewest coins that make exactly rem, or INF. */ private int fewest(int[] coins, int rem) { if (rem == 0) return 0; int best = INF; for (int coin : coins) { if (coin <= rem) { int sub = fewest(coins, rem - coin); // use this coin last if (sub != INF) best = Math.min(best, sub + 1); } } return best; }}Cache fewest(a) for every a in 0..amount.
- memo filled with −1 (unknown).
- INF stored for impossible amounts so they're not retried.
A states, each tries k coins once.
Memo + recursion depth up to A.
class Solution { private static final int INF = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { int[] memo = new int[amount + 1]; Arrays.fill(memo, -1); // -1 = not computed yet int best = fewest(coins, amount, memo); return best == INF ? -1 : best; } private int fewest(int[] coins, int rem, int[] memo) { if (rem == 0) return 0; if (memo[rem] != -1) return memo[rem]; int best = INF; for (int coin : coins) { if (coin <= rem) { int sub = fewest(coins, rem - coin, memo); if (sub != INF) best = Math.min(best, sub + 1); } } return memo[rem] = best; }}dp[a] = fewest coins for a, filled for a = 1..amount.
- dp filled with amount + 1 (acts as ∞, can't overflow).
- dp[0] = 0.
- dp[a] = min(dp[a], dp[a − c] + 1) for each coin c ≤ a.
- dp[amount] > amount → −1.
Two nested loops: amounts × coins.
One table of A + 1 ints; no stack.
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; // dp[a] = fewest coins that make a Arrays.fill(dp, amount + 1); // amount + 1 acts as "infinity": more coins than ever needed dp[0] = 0; // zero coins make amount 0 for (int a = 1; a <= amount; a++) { for (int coin : coins) { if (coin <= a && dp[a - coin] + 1 < dp[a]) { dp[a] = dp[a - coin] + 1; } } } return dp[amount] > amount ? -1 : dp[amount]; }}Fill the coin table
in the room
How to say it in the interview
talk track
- Kill greedy first: coins [1,3,4], amount 6 → greedy 4+1+1 = 3 coins, best is 3+3 = 2.
- "The last coin is one of k choices; the rest is the same problem on a smaller amount."
- Explain the
amount + 1sentinel: no answer can need more thanamountcoins (all 1s).
traps
Integer.MAX_VALUE + 1overflows to negative — never add 1 to your infinity.- Forgetting amount = 0 → 0 coins.
what they ask next
Follow-ups
Count the ways instead of the fewest coins?
That's Coin Change II (LC 518): sum instead of min, coins in the outer loop.
Return which coins?
Store the coin that improved dp[a]; walk back from amount subtracting it.
Another view?
BFS on amounts 0..A where each edge adds a coin: the first time you reach A is the fewest coins. Same O(A·k).
before you submit
Edge cases to test
- amount = 0 → 0 coins.
- Impossible: coins [2], amount 3 → −1.
- Greedy trap: [1,3,4], amount 6 → 2 (3+3), not 3.
- A coin of 2³¹ − 1: check c ≤ a before computing a − c, and never compute a + c.
practise next
Similar problems
- #518Coin Change IIMediumin Dynamic Programming
- #377Combination Sum IVMediumin Dynamic Programming
- #416Partition Equal Subset SumMediumin Dynamic Programming