Coin Change
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given coin values and an amount, return the fewest coins needed to make exactly that amount (unlimited coins of each value), or -1.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many coins do you need for amount 0?
- Hint 2For an amount, try each coin as the last coin and look up the chart for what remains.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A cashier making change. For 11 rupees they think: "if my last coin was 1, I needed the best for 10; if it was 2, the best for 9; if 5, the best for 6". They pick the smallest of these and add one coin. To be able to do that they filled a small chart from 0 rupees upward, writing the fewest coins for each amount. Amount 0 needs 0 coins.
- The obvious way
Recursion trying all coin sequences recomputes the same amounts: exponential.
- The key insight
fewest[0] = 0 and everything else starts as infinity (impossible). For each amount from 1 to the target and each coin not bigger than it: fewest[amount] = min(fewest[amount], fewest[amount - coin] + 1). If fewest[target] is still infinity, return -1.
- The algorithm
- fewest[0] = 0, others = infinity.
- For each amount, for each coin <= amount: look at fewest[amount - coin] + 1.
- Keep the smallest.
- Return fewest[target], or -1 if infinity.
Watch it run
Examplecoins = [1, 2, 5], amount = 11
Amounts 1 to 4: one coin for 1 and 2, then 3 = 2+1 (2 coins) and 4 = 2+2 (2 coins).
fewest: 0, 1, 1, 2, 2
Where people slip
- Greedy (always the biggest coin) is wrong for coin sets like [1, 3, 4] and amount 6.
- Amount 0 returns 0 coins, not -1.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def coin_change(coins, amount):
impossible = amount + 1 # more coins than ever needed
fewest = [0] + [impossible] * amount # fewest coins for each amount
for target in range(1, amount + 1):
for coin in coins:
if coin <= target:
fewest[target] = min(fewest[target], fewest[target - coin] + 1)
return fewest[amount] if fewest[amount] != impossible else -1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.