Jump to section
Coin Change asks for the fewest coins needed to make a given amount, using as many coins of each value as you like, or -1 if it cannot be done. The standard solution is bottom-up dynamic programming: work out the fewest coins for every amount from 0 upwards, each one built from a smaller amount plus one coin. It runs in O(amount × number of coins) time and O(amount) space.
The Problem
You are given a list of coin values and a target amount. You can use each coin value as many times as you like. Return the smallest number of coins that add up exactly to the amount, or -1 if no combination works.
Example 1
Input: coins = [1, 2, 5], amount = 11
Output: 3
Why: 5 + 5 + 1 = 11 uses three coins, and no two coins reach 11.
Example 2
Input: coins = [2], amount = 3
Output: -1
Why: only even totals can be made from 2s.
Assumptions to confirm
- Can each coin value be used more than once? (Yes, as often as you like, in the classic version.)
- What does amount 0 return? (0 coins.)
- Are coin values positive? (Assume yes.)
- Do you want the count or the coins themselves? (The count; listing the coins is a follow-up.)
Start With the Brute Force
The natural first idea is greedy: always take the largest coin that fits. It works for everyday currencies, so say why it fails in general. With coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 (three coins), but 3 + 3 uses two.
The correct brute force tries every coin at every step, recursively: the answer for an amount is 1 plus the best answer for the amount minus each coin. That is exponential, because the same smaller amounts are solved again and again. Recognising those repeated subproblems is exactly what leads to dynamic programming.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
The Optimal Approach: Bottom-Up Dynamic Programming
Define the subproblem
dp[a] is the fewest coins needed to make amount a.
Set the base case
dp[0] = 0. Every other amount starts at a sentinel that means "not reachable yet", such as amount + 1.
Fill the table from small to large
For each amount a, try every coin no larger than a: dp[a] = min(dp[a], dp[a - coin] + 1).
Read the answer
If dp[amount] is still the sentinel, return -1; otherwise return dp[amount].
Solution in Python and TypeScript
Both versions use amount + 1 as the "impossible" value: you can never need more coins than the amount itself when the smallest coin is 1, so anything larger means unreachable.
Python
def coin_change(coins: list[int], amount: int) -> int:
INF = amount + 1 # more coins than could ever be needed
dp = [0] + [INF] * amount # dp[a] = fewest coins to make a
for a in range(1, amount + 1):
for coin in coins:
if coin <= a and dp[a - coin] + 1 < dp[a]:
dp[a] = dp[a - coin] + 1
return dp[amount] if dp[amount] != INF else -1TypeScript
function coinChange(coins: number[], amount: number): number {
const INF = amount + 1; // more coins than could ever be needed
const dp = new Array<number>(amount + 1).fill(INF); // dp[a] = fewest coins to make a
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) dp[a] = dp[a - coin] + 1;
}
}
return dp[amount] === INF ? -1 : dp[amount];
}The top-down version, a recursive function with a memo, gives the same complexity and is often easier to explain first. Bottom-up avoids deep recursion for large amounts.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Time and Space Complexity
| Approach | Time | Space | When to use it |
|---|---|---|---|
| Greedy (largest coin first) | O(amount) | O(1) | Only for coin systems known to be greedy-safe |
| Plain recursion | Exponential | O(amount) stack | Only as your first spoken answer |
| Recursion with a memo | O(amount × coins) | O(amount) | Easy to derive from the recursion |
| Bottom-up table | O(amount × coins) | O(amount) | The expected interview answer |
How to Talk Through Coin Change in an Interview
- Clarify: "Can I reuse each coin value? Count or the coins themselves? What if it is impossible?"
- Brute force: "Greedy fails for coins like 1, 3, 4. The safe brute force tries every coin recursively, but solves the same amounts many times."
- Optimise: "I will solve every amount from 0 up and reuse smaller answers. Each amount is the best of one more coin on top of a smaller amount."
- Code: explain the sentinel value and the -1 at the end.
- Test: [1, 2, 5] with 11, [2] with 3, and amount 0. State O(amount × coins) time and O(amount) space.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Edge Cases and Common Follow-Ups
Amount 0
Return 0 without any coins.
Unreachable amounts
Return -1. Using a sentinel bigger than any real answer keeps the min comparison simple.
Count the ways instead
Coin Change II asks how many combinations make the amount. Loop over coins in the outer loop so each combination is counted once.
List the coins used
Store which coin improved each dp[a], then walk back from the amount.
Very large amounts
Ask about limits. Breadth-first search over amounts is an alternative that stops as soon as the amount is reached.
Practise Coin Change in a Mock Coding Round
Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Coin Change out loud, under time pressure, while explaining each decision.
MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).
Frequently Asked Questions
Why does the greedy approach fail for coin change?
What is the time complexity of the coin change DP?
What is the difference between Coin Change and Coin Change II?
Should I write it top-down or bottom-up?
Why use amount + 1 as the impossible value?
Stop Preparing in Your Head. Start Practicing Out Loud.
Drop your resume, add a job description, and get a mock interview like the real thing.
Start Free Mock Interview →Still applying for jobs? Let Auto Apply do it for you.