Coin Change
Problem statement
You are given a list of coin values coins and a target amount. You have an unlimited supply of every coin. Return the fewest coins that add up to exactly amount, or -1 if no combination of coins can make it. An amount of 0 needs 0 coins.
The same question comes up in capacity planning: you can only buy instances in fixed sizes (say 2, 4 and 16 vCPUs), you need exactly 36 vCPUs, and you want as few machines as possible — or to know that the exact number is impossible.
Examples
Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 5 + 5 + 1 = 11 uses 3 coins. No choice of 2 coins reaches 11 — the most two coins can make is 5 + 5 = 10.
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: With only 2-coins, every total is even, so 3 can never be made.
Example 3
Input: coins = [1], amount = 0
Output: 0
Explanation: An amount of 0 is already reached before picking any coin, so the answer is 0 coins.
Hints
[1,3,4] and amount 6. What does greedy give, and what's the real answer?Approach
Optimal: Bottom-up DP
Intuition
Flip the order around. Instead of starting at amount and recursing down, start at 0 and build up. best[0] = 0. For each amount a from 1 upward, every smaller amount is already solved, so best[a] is 1 plus the smallest best[a − c] over the coins that fit. By the time we reach amount, its slot holds the answer.
This is bottom-up dynamic programming. It computes exactly the same values as the memo version, just in a planned order, with a loop instead of recursion. Mark impossible amounts with a value bigger than any real answer — amount + 1 works, because even using only 1-coins needs at most amount coins.
Steps
- Create
bestwithamount + 1slots, all set toamount + 1("impossible"). Setbest[0] = 0. - For each
afrom 1 toamount:- For each coin
cwithc <= a: setbest[a] = min(best[a], best[a − c] + 1).
- For each coin
- If
best[amount]is stillamount + 1, return-1; otherwise return it.
Dry run
coins = [1,2,5], amount = 11
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| best[a] | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
For example, best[11] = min(best[10], best[9], best[6]) + 1 = min(2, 3, 2) + 1 = 3. For coins = [2], amount = 3, the odd amounts stay at "impossible", so the answer is -1.
Complexity
Time O(a·k) - We fill one table slot for each amount from 1 to a, and each slot tries all k coins. That is a × k steps, the same as the memoised version. It has no function-call overhead, so it is faster in practice. For amount 10,000 and 12 coins that is 120,000 simple steps.
Space O(a) - The table has `a + 1` slots. There is no recursion, so there is no risk of a stack overflow however large the amount is. The input is not counted.
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
impossible = amount + 1
best = [impossible] * (amount + 1)
best[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return -1 if best[amount] == impossible else best[amount]
if __name__ == "__main__":
print(Solution().coinChange([1, 2, 5], 11)) # 3
print(Solution().coinChange([2], 3)) # -1
print(Solution().coinChange([1], 0)) # 0RecapThe whole problem in a few lines, for the night before
- Spot it: fewest items that add up to an exact total, any item reusable
- Idea:
best[a]= fewest coins for amounta; try every coin as the last one:best[a] = 1 + min(best[a − c]) - Cost: O(amount × coins) time, O(amount) space
- Trap: greedy (largest coin first) fails for coins like [1, 3, 4] and amount 6
- Remember: use
amount + 1as "impossible" to avoid overflow;best[0] = 0
Interview follow-ups
Return the coins used, not just how many.
Keep a second array
last[a]holding the coin that gave the best answer for amounta. Walk back fromamount: takelast[amount], subtract it, and repeat until you reach 0. Time stays O(a·k) and the extra array is O(a). In capacity planning, that is the actual list of instance sizes to buy.Count how many different combinations make the amount instead.
That is Coin Change II. Use
ways[0] = 1, and loop over coins on the outside and amounts on the inside, addingways[a − c]toways[a]. Putting coins outside counts each combination once regardless of order. The time is the same O(a·k).Each coin can only be used a limited number of times. What changes?
Now it is a bounded knapsack problem. The simplest fix is to treat each copy of a coin as a separate item and process items one at a time, looping amounts from high to low so an item isn't reused. Time becomes O(a × total number of coin copies). For large counts, splitting each count into powers of two (1, 2, 4, …) keeps it fast.
Frequently asked questions
Greedy works for everyday currencies, but not for every set of coins. With coins [1,3,4] and amount 6, greedy takes 4, then 1, then 1 — three coins — while 3 + 3 uses only two. Taking a big coin early can leave an awkward remainder. The DP tries every coin as the last one, so it can't be fooled this way.
The worst possible real answer uses only 1-coins, which is amount coins. So no real answer is ever amount + 1 or more. Using it instead of "infinity" also avoids overflow in Java and C++: Integer.MAX_VALUE + 1 wraps around to a negative number and breaks the min.
They compute the same values with the same O(a·k) cost. Memoisation is an easy step from the brute force and only solves the amounts it actually needs. Bottom-up avoids recursion, so it can't overflow the stack for amounts like 10,000 — a real risk in Python and Java, where the memoised version can crash at the largest inputs. It is usually faster too. Interviewers are happy with either if you can explain it.
Yes. Treat each amount as a node and each coin as a step that subtracts its value. A BFS from amount finds the fewest steps to reach 0, because every step costs one coin. It has the same O(a·k) worst case and can stop early when the answer is small. The DP is more common, but mentioning BFS shows you see the graph behind it.
It's capacity planning with fixed sizes: the fewest instances, disks or node types that add up to an exact capacity — or the fact that it can't be done exactly. It is also the standard first dynamic-programming problem, and an interview for a software-engineering-heavy infra role often includes one DP question like it.