Coin Change
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart
Problem
You are given coins of different denominations and a total amount. Write a function to compute the fewest number of coins needed to make up that amount. If it is not possible, return -1.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
This is an unbounded knapsack variant. You can use each coin unlimited times. dp[i] = minimum coins to make amount i.
The recurrence: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin where coin <= i. You're checking "if I use this coin, how many more do I need?"
Base case: dp[0] = 0 (zero coins needed for amount 0). Fill dp[1] through dp[amount] left to right.
Why bottom-up works: to compute dp[i], you need dp[i-coin] which is a smaller amount. By filling left to right, smaller amounts are always computed first.
Visual walkthrough for coins=[1,2,5], amount=5:
dp[0]=0, dp[1..5]=inf
i=1: coin 1: dp[1]=min(inf, dp[0]+1)=1
i=2: coin 1: dp[2]=min(inf, dp[1]+1)=2. coin 2: dp[2]=min(2, dp[0]+1)=1.
i=3: coin 1: dp[3]=min(inf, dp[2]+1)=2. coin 2: dp[3]=min(2, dp[1]+1)=2.
i=4: coin 1: dp[4]=min(inf, dp[3]+1)=3. coin 2: dp[4]=min(3, dp[2]+1)=2.
i=5: coin 1: dp[5]=min(inf, dp[4]+1)=3. coin 2: dp[5]=min(3, dp[3]+1)=3. coin 5: dp[5]=min(3, dp[0]+1)=1.
Result: 1 (one coin of value 5)
Edge cases: amount=0 (return 0), no valid combination (return -1), single coin denomination.
Optimal Approach
Step 1: Create dp array of size amount+1, fill with infinity. dp[0] = 0.
Step 2: For i from 1 to amount:
For each coin where coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
Step 3: Return dp[amount] if not infinity, else -1.
The logic: if you use a coin of value "coin", you need 1 coin plus however many coins were needed for amount "i - coin".
Time: O(amount × number of coins). Space: O(amount).
What Trips People Up in Real Interviews
Confusing "minimum coins" with "counting ways." This problem asks for the fewest coins, not the number of ways to make the amount.
Not handling the case where no combination works. Return -1, not 0 or null.
Forgetting to initialize dp[0] = 0. Zero coins are needed to make amount 0.
Using BFS instead of DP. BFS works (each level is one more coin) but DP is simpler and more efficient for this problem.
Filling the dp array in the wrong order. You must fill left to right (dp[0] to dp[amount]) because each dp[i] depends on smaller amounts (dp[i - coin]). Filling right to left gives wrong results.
Solution Code
def coinChange(coins, amount):
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 -1Frequently Asked Questions
What is the Coin Change problem?
You are given coins of different denominations and a total amount. Write a function to compute the fewest number of coins needed to make up that amount. If it is not possible, return -1.
How do you solve Coin Change?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Coin Change?
Coin Change is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart. It is a medium difficulty problem.
What are common mistakes on Coin Change?
- Confusing "minimum coins" with "counting ways." This problem asks for the fewest coins, not the number of ways to make the amount.
- Not handling the case where no combination works. Return -1, not 0 or `null`.
- Forgetting to initialize `dp[0]` = 0. Zero coins are needed to make amount 0.
- Using BFS instead of DP. BFS works (each level is one more coin) but DP is simpler and more efficient for this problem.
- Filling the dp array in the wrong order. You must fill left to right (`dp[0]` to `dp[amount]`) because each `dp[i]` depends on smaller amounts (`dp[i - coin]`). Filling right to left gives wrong results.