The problem
Given coin values and an amount, find the fewest coins that add up to the amount exactly (unlimited coins of each value). Return −1 if impossible.
Input: coins = [1, 3, 4], amount = 6 Output: 2 (3 + 3; greedy 4 + 1 + 1 would use 3)
Picture it
Picture a row of boxes labelled ₹0, ₹1, ₹2 … up to the amount. Each box will hold the fewest coins needed to make that amount. To fill box x, try each coin c: “one coin c plus the best way to make x − c”. Take the smallest. Box ₹0 needs no coins. Taking the biggest coin first (greedy) can fail, which is why we check every coin.
How to recognise it
- You need the minimum number of items (coins) that add to an exact total, with each item reusable.
- Picking the largest coin first is tempting but wrong for general coin sets, so greedy is a trap here.
- The best answer for an amount is built from the best answers for smaller amounts:
fewest[a]depends onfewest[a - c]for each coin c. - Amount up to 10^4 and up to 12 coin kinds: about 10^5 table steps, but an exponential number of coin sequences.
- "Fewest pieces to reach a total" with unlimited reuse is the classic 1-D dynamic programming (DP) shape.
Start with brute force
Try every coin as the next one and recurse on what is left. Keep the smallest count found; if no coin sequence reaches the amount, report −1.
def coin_change_brute(coins, amount):
def go(left): # fewest coins to make `left`, or None
if left == 0:
return 0
best = None
for c in coins:
if c <= left:
sub = go(left - c)
if sub is not None and (best is None or sub + 1 < best):
best = sub + 1
return best
r = go(amount)
return -1 if r is None else r
Every call can start one call per coin, so the work grows exponentially. With coins 1, 2 and 5 it already takes about 13 million calls for amount 30 and about 2 × 10^23 for amount 100, while the real limit is 10,000. Space is O(amount) for the recursion.
From brute force to the idea
- Find the waste. Many different coin orders leave the same remainder, and the brute force solves that remainder again each time.
- Define a table.
fewest[a]is the smallest number of coins that make amount a.fewest[0] = 0, and unreached amounts start at infinity. - Try the last coin. For each coin c not bigger than a, one coin plus the best for
a - cis a candidate:fewest[a - c] + 1. Keep the minimum. - Convert at the end. If
fewest[amount]is still infinity, nothing reached it, so return −1.
Note: the shown code uses inf but does not import it. It needs from math import inf at the top.
This is the key idea: build the answers for amounts 1, 2, 3, … in order, each from one coin plus a smaller answer already stored.
The key idea
best[x] = 1 + min(best[x − c]) over coins c. O(amount × coins).
Python solution
def coin_change(coins, amount):
fewest = [0] + [inf] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
n = fewest[a - c] + 1
fewest[a] = min(fewest[a], n)
best = fewest[amount]
return -1 if best == inf else bestLeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential: one branch per coin at every level, same remainders re-solved | O(amount): recursion depth |
| Table (shown code) | O(amount × number of coins): about 1.2 × 10^5 steps at the limits | O(amount): the fewest list |
Edge cases
- Amount 0: returns
0, no coins needed (fewest[0]), even if the coin list is odd. - Impossible amount (
[2], 3): returns-1. - Exact single coin (
[1], 2 → 2;[5], 5 → 1). - Greedy trap (
[1, 3, 4], 6): returns2(3 + 3), where greedy gives 4 + 1 + 1 = 3 coins. - Coins larger than the amount: skipped by
c <= a. Without that test, a negative index would silently read from the end of the list. - Unsorted or duplicate coins (
[3, 3, 2], 7): returns3(3 + 2 + 2); order and repeats do not matter. - Large example (
[186, 419, 83, 408], 6249): returns20.
Common mistakes
- Taking the biggest coin first. With
[1, 3, 4]and 6 that uses three coins instead of two. - Starting the table with
fewest[0] = inf, so nothing is ever reachable and every answer is −1. - Returning
fewest[amount]directly, which givesinf, not −1, for impossible amounts. - Leaving out the
c <= acheck.
Instead of the fewest coins, count the ordered sequences of coins that add up to the amount (so 1+2 and 2+1 are different). For coins [1, 2, 3] and amount 4 the answer is 7. Describe your approach, then write it if you like.
Compare with our answer
Same table, but add the sub-answers instead of taking a minimum, and start with one way to make 0.
def count_orders(coins, amount):
ways = [1] + [0] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
ways[a] += ways[a - c]
return ways[amount]
count_orders([1, 2, 3], 4) is 7, count_orders([2], 3) is 0 and count_orders([1, 3, 4], 6) is 9. Time O(amount × coins), space O(amount).
A strong answer mentions: ways[0] = 1 (the empty sequence), summing over every coin that fits, the coin loop being inside the amount loop (this is what makes order matter), and that the counts can get large.
1. You must find the fewest coins that make an exact amount from arbitrary coin values, such as 1, 3 and 4, with amounts up to 10,000. Which approach fits best?
The best answer for each amount comes from one coin plus a smaller best answer, so a table solves it in O(amount × coins). Greedy fails on 1, 3, 4 with 6, and trying every sequence is exponential.
2. What is the time complexity of the shown code with A as the amount and k as the number of coin kinds?
There are two loops, A amounts by k coins, each doing constant work. O(A²) would need each amount to look at every smaller amount, and O(k^A) is the brute force.
3. A learner returns fewest[amount] without the -1 if best == inf conversion. Which input now gives a different result?
With only coin 2, amount 3 is unreachable, so the table holds inf and the learner's version returns infinity instead of −1. In the other cases the amount is reachable, so the value is the same (3, 0 and 2).
Score 60% or more and the lesson is marked complete.