Coin Change
Find the fewest coins that add up to an amount, with unlimited coins of each value. The textbook case where greedy fails and bottom-up dynamic programming works. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You have an unlimited supply of coins of each value in coins. Return the fewest coins whose values add up to exactly amount.
If no combination of coins makes amount, return -1. An amount of 0 needs zero coins.
Example 1
- Input
- coins = [1, 4, 6], amount = 8
- Output
- 2
4 + 4 uses two coins. Grabbing the biggest coin first gives 6 + 1 + 1, which uses three.
Example 2
- Input
- coins = [3, 7], amount = 5
- Output
- -1
No mix of 3s and 7s adds up to 5.
Example 3
- Input
- coins = [2], amount = 0
- Output
- 0
Constraints
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 10⁴, and the values are distinct.
- 0 ≤ amount ≤ 10⁴
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Coin Change in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Coin Change
Pattern: Bottom-up DP over amounts
The tempting move is greedy: always take the biggest coin that fits. With coins [1, 4, 6] and amount 8, greedy takes 6 + 1 + 1 (three coins) and misses 4 + 4 (two). Once you see one counterexample, you know you have to consider every coin at every step.
The structure that makes this tractable: if the best way to make a ends with coin c, then the rest of it is the best way to make a - c. So
best[a] = 1 + min(best[a - c] for each coin c ≤ a)
with best[0] = 0. There are only amount + 1 distinct subproblems, so you can fill them in order from 0 up and each one only looks at smaller amounts that are already done. Amounts that can't be made stay at "infinity".
Approach 1: Plain recursion
Try every coin as the last one and recurse on the remainder, taking the minimum. Correct, but the same remainders get solved again and again, so it blows up exponentially.
Time O(kᵃ) for k coins and amount a · Space O(a) recursion
Approach 2: Recursion with memoization
Cache the answer for each remaining amount. That brings it down to O(a · k), but the recursion can go about amount levels deep (10⁴ with a coin of 1), which overflows the default Python stack.
Time O(a · k) · Space O(a)
Approach 3: Bottom-up table
- Make
bestof lengthamount + 1, filled withamount + 1(a value larger than any real answer), and setbest[0] = 0. - For each
afrom 1 toamount, and each coinc ≤ a:best[a] = min(best[a], best[a - c] + 1). - Return
best[amount]if it is at mostamount, otherwise-1.
Using amount + 1 as the sentinel avoids infinity arithmetic: no real answer can be that large, since the smallest coin is at least 1.
Time O(a · k) · Space O(a)
| Approach | Time | Space |
|---|---|---|
| Plain recursion | O(kᵃ) for k coins and amount a | O(a) recursion |
| Recursion with memoization | O(a · k) | O(a) |
| Bottom-up table | O(a · k) | O(a) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Coin Change solution in Python
def coin_change(coins: list[int], amount: int) -> int:
unreachable = amount + 1
best = [0] + [unreachable] * amount
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 best[amount] if best[amount] != unreachable else -1Coin Change solution in JavaScript
function coinChange(coins, amount) {
const unreachable = amount + 1;
const best = new Array(amount + 1).fill(unreachable);
best[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
}
}
return best[amount] === unreachable ? -1 : best[amount];
}Common mistakes
- Using greedy, which fails on coin sets like [1, 4, 6] or [25, 10, 1].
- Forgetting `best[0] = 0`, so nothing can ever be built.
- Adding 1 to an "infinity" sentinel in a language where that overflows, or returning the sentinel instead of -1.
- Writing the memoized recursion and hitting the recursion limit on amounts near 10⁴.
- Treating it like a combinations-counting problem and swapping the loop order without thinking; for a minimum, either order works, but for counting ways it matters.
What interviewers look for
Open with a counterexample to greedy. It's the fastest way to show the interviewer you know why this needs DP. Then state the recurrence in one line and the base case, and say how many subproblems there are; that sentence gives you the complexity.
If you start top-down with memoization, mention the recursion depth and offer to convert it to the bottom-up table. Interviewers like hearing that you know where each version breaks.
Follow-up questions
How would you count the number of ways to make the amount instead?
Use ways[0] = 1 and, looping over coins in the outer loop and amounts in the inner loop, add ways[a - c] into ways[a]. Coins outside means each combination is counted once regardless of order.
How would you return the actual coins, not just the count?
Store, for each amount, the coin that produced its best value. Then walk back from amount: take that coin, subtract it, and repeat until you reach 0.
What if each coin can be used at most once?
It becomes a 0/1 knapsack. Loop over coins in the outer loop and over amounts from high to low in the inner loop, so each coin contributes to a given amount at most once.
Companies that ask Coin Change
Coin Change is tagged by 123 companies in our interview dataset. The score shows how often it comes up at each company.
- Glassdoor100%
- Skillz100%
- Upwork100%
- Mcdonalds100%
- Nference98%
- Shipt95%
- Datadog93.8%
- Boeing90%
- Abbott87%
- Mastercard86.1%
- Fis83%
- Zulily81%
- Sigmoid80%
- Geico79.9%
- Prove79%
- Freshbooks78%
- Wex78%
- Pinterest77%
- Moderna77%
- SpaceX77%
- Culture Amp75%
- Gigamon75%
- C3.ai75%
- Trellix74%
and 99 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required