You're at a till handing back change. You have an unlimited stack of each coin in front of you — say 1s, 2s, and 5s — and you owe the customer some amount. You want to hand over the fewest coins that add up exactly to that amount. Implement coinChange(coins, amount): given the available denominations and a target, return the smallest number of coins that sum to amount, or -1 if no combination of those coins can make it.
The catch that makes this more than counting: grabbing the biggest coin that fits, over and over, does not always give the fewest coins. With coins [1, 3, 4] and a target of 6, biggest-first hands back 4 + 1 + 1 (three coins) when 3 + 3 (two coins) is better. You need to consider every denomination at every step, not just the largest.
// coins: number[] — available denominations, each a positive integer.
// You have an UNLIMITED supply of each.
// amount: number — the target total to make (a non-negative integer).
// returns: number — the FEWEST coins that sum to `amount`,
// or -1 if no combination can make it.
function coinChange(coins, amount): number;// 5 + 5 + 1 = 11 uses three coins; nothing does it in two.
coinChange([1, 2, 5], 11); // → 3// 3 + 3 = 6 in two coins. Biggest-first (4 + 1 + 1) would say three — wrong.
coinChange([1, 3, 4], 6); // → 2// Every total made from 2s is even, so 3 is unreachable.
coinChange([2], 3); // → -1// Making zero needs zero coins, regardless of the denominations.
coinChange([1, 2, 5], 0); // → 0amount of 0 returns 0. The empty selection sums to zero, so no coins are needed.-1. If no combination sums exactly to amount (e.g. only [2] to make 3), return -1 — not 0, not Infinity.coins is sorted or deduplicated; your answer must not depend on either.You'll find the fewest coins that sum to a target by solving the same question for every smaller amount first, then building the answer for the target out of those.
You owe a customer some amount of change, and you have an unlimited pile of each coin denomination. You want to hand over as few physical coins as possible. With friendly coins like [1, 2, 5] the "grab the biggest one that fits" instinct happens to work — but the coins are not always friendly. The whole difficulty of this problem is that the obvious greedy move is wrong for some denomination sets, and proving you've found the true minimum means checking more than one option at every step.
Don't think about the target all at once. Instead, ask the same small question for every amount from 0 up to the target: what is the fewest coins to make exactly this amount? Call the answer for amount a the value dp[a]. Once you know dp for every amount smaller than a, computing dp[a] is easy: try each coin c as the last coin you place. If you spend a coin worth c, you still owe a - c, and the best way to make that is a number you already worked out — dp[a - c]. So dp[a] is one (for the coin you just spent) plus the best dp[a - c] over every coin that fits.
This is bottom-up dynamic programming: solve the smallest sub-problems first, store each answer in a table, and reuse it instead of recomputing. The base case anchors everything — dp[0] = 0, because making zero takes zero coins.
The natural first instinct is greedy: always take the largest coin that still fits, then repeat on what's left. It's how you'd actually make change at a till, and for real-world currency systems it genuinely works.
function coinChangeGreedy(coins, amount) {
const sorted = [...coins].sort((a, b) => b - a); // biggest first
let remaining = amount;
let count = 0;
for (const coin of sorted) {
while (coin <= remaining) {
remaining -= coin; // take this coin
count++;
}
}
return remaining === 0 ? count : -1;
}This passes the easy cases and then quietly returns the wrong answer. Run it on coins = [1, 3, 4], amount = 6. Biggest-first grabs a 4 (remaining 2), then 4 and 3 are both too big, so it falls to 1 twice (remaining 0). It reports 4 + 1 + 1 — three coins. But 3 + 3 makes 6 in two. Greedy committed to the 4 and could never take it back, even though skipping it was the better move.
You could try to fix this by exploring every choice with recursion instead — at each amount, try every coin and recurse on the remainder, then keep the smallest result. That is correct, but it recomputes the same sub-amounts over and over: making amount branches into amount - c for every coin, and those branches overlap heavily, so the work grows exponentially. Making 30 from [1, 2, 5] explores millions of redundant paths. The recursion has the right idea — try every coin — but no memory.
Keep "try every coin," throw away both the greedy commitment and the redundant recomputation. Fill a table from 0 up to amount, and each cell reuses the cells below it exactly once.
function coinChange(coins, amount) {
// dp[a] = fewest coins to make exactly `a`. Infinity = "not reachable yet".
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // base case: making zero takes zero coins
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
// Only coins that fit can be the last coin placed.
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1; // spend `coin`, then best way to make the rest
}
}
}
// Still Infinity → no combination of coins sums to `amount`.
return dp[amount] === Infinity ? -1 : dp[amount];
}
module.exports = { coinChange };The shifts from the naive versions are worth naming. Infinity is the "unreachable" marker. Every amount starts unreachable; only dp[0] is seeded to 0. If an amount can't be built from any coin, its cell stays Infinity to the end, and the final line maps that to -1. The outer loop walks amounts in increasing order, which guarantees dp[a - coin] is already final before we read it — that ordering is what lets one pass replace the exponential recursion. The coin <= a guard skips coins too big to be the last one placed; without it, a - coin goes negative and indexes off the front of the array. And note the relaxation is a real comparison: we keep dp[a] if a coin doesn't improve it, so trying coins in any order lands on the same minimum.
One subtlety in dp[a - coin] + 1 < dp[a]: if dp[a - coin] is Infinity (that sub-amount is itself unreachable), then Infinity + 1 is still Infinity, which is never less than the current dp[a], so the unreachable path correctly contributes nothing.
Take coinChange([1, 2, 5], 6). We fill dp[0..6] left to right. At each cell we try every coin c <= a and keep the smallest dp[a - c] + 1.
dp[0] = 0 base case
dp[1]: coin 1 → dp[0] + 1 = 1 dp[1] = 1
(coins 2, 5 don't fit)
dp[2]: coin 1 → dp[1] + 1 = 2
coin 2 → dp[0] + 1 = 1 ← better dp[2] = 1
dp[3]: coin 1 → dp[2] + 1 = 2
coin 2 → dp[1] + 1 = 2 dp[3] = 2
dp[4]: coin 1 → dp[3] + 1 = 3
coin 2 → dp[2] + 1 = 2 ← better dp[4] = 2
dp[5]: coin 1 → dp[4] + 1 = 3
coin 2 → dp[3] + 1 = 3
coin 5 → dp[0] + 1 = 1 ← better dp[5] = 1
dp[6]: coin 1 → dp[5] + 1 = 2
coin 2 → dp[4] + 1 = 3
coin 5 → dp[1] + 1 = 2 dp[6] = 2
Final array: [0, 1, 1, 2, 2, 1, 2]. dp[6] = 2 is not Infinity, so we return 2 — making 6 takes two coins (5 + 1, the path through dp[5]). Notice dp[5] = 1 did the heavy lifting twice: once for itself (a single 5) and again as the cheap remainder when dp[6] spent a 1. That reuse is the entire point of the table.
The contrast with greedy and naive recursion is worth holding onto: greedy would commit to one coin per step and never reconsider; the table tries every coin at every amount but only computes each sub-amount once.
[1, 5, 10, 25] but fails for sets like [1, 3, 4] (where 6 is 3 + 3, not 4 + 1 + 1). Unless you can prove the denomination set is canonical, use DP. When in doubt, DP.dp[0] must be 0, not Infinity. This is the base case the whole table stands on. If you leave dp[0] unreachable, then dp[c] for a coin c computes dp[0] + 1 = Infinity, every cell stays unreachable, and a perfectly solvable input returns -1.-1, not Infinity or 0, when unreachable. A cell that never improved stays Infinity. Map that to -1 on the way out. Returning Infinity leaks an internal sentinel; returning 0 falsely claims "made with zero coins." The amount-0 case is the only legitimate 0.coin <= a before indexing dp[a - coin]. Skip coins larger than the current amount. A coin of 10 can't be the last coin placed toward making 3; without the guard, a - coin is negative and dp[-7] is undefined, poisoning the comparison.Infinity + 1 is still Infinity — lean on it. When dp[a - coin] is unreachable, dp[a - coin] + 1 stays Infinity and never wins the comparison, so unreachable remainders contribute nothing automatically. No special-casing needed; just don't write code that breaks this (e.g. capping at a fixed large integer that can overflow past a real answer).amount + 1, not amount. You need an index for every amount from 0 through amount inclusive. Allocating amount slots drops dp[amount] off the end and reads undefined.from array recording which coin improved each dp[a]. After filling the table, start at amount and repeatedly subtract from[a] until you reach 0, collecting the coins — this reconstructs one optimal combination in O(amount).ways[a] += ways[a - coin], and crucially the coin loop goes outside the amount loop so each denomination is considered once and you count combinations, not ordered sequences. A classic follow-up that looks identical but flips the loop nesting.solve(remaining) result in a Map. Same O(amount × coins) work as the bottom-up table, often more intuitive to write, at the cost of recursion-stack depth on large amounts.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're at a till handing back change. You have an unlimited stack of each coin in front of you — say 1s, 2s, and 5s — and you owe the customer some amount. You want to hand over the fewest coins that add up exactly to that amount. Implement coinChange(coins, amount): given the available denominations and a target, return the smallest number of coins that sum to amount, or -1 if no combination of those coins can make it.
The catch that makes this more than counting: grabbing the biggest coin that fits, over and over, does not always give the fewest coins. With coins [1, 3, 4] and a target of 6, biggest-first hands back 4 + 1 + 1 (three coins) when 3 + 3 (two coins) is better. You need to consider every denomination at every step, not just the largest.
// coins: number[] — available denominations, each a positive integer.
// You have an UNLIMITED supply of each.
// amount: number — the target total to make (a non-negative integer).
// returns: number — the FEWEST coins that sum to `amount`,
// or -1 if no combination can make it.
function coinChange(coins, amount): number;// 5 + 5 + 1 = 11 uses three coins; nothing does it in two.
coinChange([1, 2, 5], 11); // → 3// 3 + 3 = 6 in two coins. Biggest-first (4 + 1 + 1) would say three — wrong.
coinChange([1, 3, 4], 6); // → 2// Every total made from 2s is even, so 3 is unreachable.
coinChange([2], 3); // → -1// Making zero needs zero coins, regardless of the denominations.
coinChange([1, 2, 5], 0); // → 0amount of 0 returns 0. The empty selection sums to zero, so no coins are needed.-1. If no combination sums exactly to amount (e.g. only [2] to make 3), return -1 — not 0, not Infinity.coins is sorted or deduplicated; your answer must not depend on either.You'll find the fewest coins that sum to a target by solving the same question for every smaller amount first, then building the answer for the target out of those.
You owe a customer some amount of change, and you have an unlimited pile of each coin denomination. You want to hand over as few physical coins as possible. With friendly coins like [1, 2, 5] the "grab the biggest one that fits" instinct happens to work — but the coins are not always friendly. The whole difficulty of this problem is that the obvious greedy move is wrong for some denomination sets, and proving you've found the true minimum means checking more than one option at every step.
Don't think about the target all at once. Instead, ask the same small question for every amount from 0 up to the target: what is the fewest coins to make exactly this amount? Call the answer for amount a the value dp[a]. Once you know dp for every amount smaller than a, computing dp[a] is easy: try each coin c as the last coin you place. If you spend a coin worth c, you still owe a - c, and the best way to make that is a number you already worked out — dp[a - c]. So dp[a] is one (for the coin you just spent) plus the best dp[a - c] over every coin that fits.
This is bottom-up dynamic programming: solve the smallest sub-problems first, store each answer in a table, and reuse it instead of recomputing. The base case anchors everything — dp[0] = 0, because making zero takes zero coins.
The natural first instinct is greedy: always take the largest coin that still fits, then repeat on what's left. It's how you'd actually make change at a till, and for real-world currency systems it genuinely works.
function coinChangeGreedy(coins, amount) {
const sorted = [...coins].sort((a, b) => b - a); // biggest first
let remaining = amount;
let count = 0;
for (const coin of sorted) {
while (coin <= remaining) {
remaining -= coin; // take this coin
count++;
}
}
return remaining === 0 ? count : -1;
}This passes the easy cases and then quietly returns the wrong answer. Run it on coins = [1, 3, 4], amount = 6. Biggest-first grabs a 4 (remaining 2), then 4 and 3 are both too big, so it falls to 1 twice (remaining 0). It reports 4 + 1 + 1 — three coins. But 3 + 3 makes 6 in two. Greedy committed to the 4 and could never take it back, even though skipping it was the better move.
You could try to fix this by exploring every choice with recursion instead — at each amount, try every coin and recurse on the remainder, then keep the smallest result. That is correct, but it recomputes the same sub-amounts over and over: making amount branches into amount - c for every coin, and those branches overlap heavily, so the work grows exponentially. Making 30 from [1, 2, 5] explores millions of redundant paths. The recursion has the right idea — try every coin — but no memory.
Keep "try every coin," throw away both the greedy commitment and the redundant recomputation. Fill a table from 0 up to amount, and each cell reuses the cells below it exactly once.
function coinChange(coins, amount) {
// dp[a] = fewest coins to make exactly `a`. Infinity = "not reachable yet".
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // base case: making zero takes zero coins
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
// Only coins that fit can be the last coin placed.
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1; // spend `coin`, then best way to make the rest
}
}
}
// Still Infinity → no combination of coins sums to `amount`.
return dp[amount] === Infinity ? -1 : dp[amount];
}
module.exports = { coinChange };The shifts from the naive versions are worth naming. Infinity is the "unreachable" marker. Every amount starts unreachable; only dp[0] is seeded to 0. If an amount can't be built from any coin, its cell stays Infinity to the end, and the final line maps that to -1. The outer loop walks amounts in increasing order, which guarantees dp[a - coin] is already final before we read it — that ordering is what lets one pass replace the exponential recursion. The coin <= a guard skips coins too big to be the last one placed; without it, a - coin goes negative and indexes off the front of the array. And note the relaxation is a real comparison: we keep dp[a] if a coin doesn't improve it, so trying coins in any order lands on the same minimum.
One subtlety in dp[a - coin] + 1 < dp[a]: if dp[a - coin] is Infinity (that sub-amount is itself unreachable), then Infinity + 1 is still Infinity, which is never less than the current dp[a], so the unreachable path correctly contributes nothing.
Take coinChange([1, 2, 5], 6). We fill dp[0..6] left to right. At each cell we try every coin c <= a and keep the smallest dp[a - c] + 1.
dp[0] = 0 base case
dp[1]: coin 1 → dp[0] + 1 = 1 dp[1] = 1
(coins 2, 5 don't fit)
dp[2]: coin 1 → dp[1] + 1 = 2
coin 2 → dp[0] + 1 = 1 ← better dp[2] = 1
dp[3]: coin 1 → dp[2] + 1 = 2
coin 2 → dp[1] + 1 = 2 dp[3] = 2
dp[4]: coin 1 → dp[3] + 1 = 3
coin 2 → dp[2] + 1 = 2 ← better dp[4] = 2
dp[5]: coin 1 → dp[4] + 1 = 3
coin 2 → dp[3] + 1 = 3
coin 5 → dp[0] + 1 = 1 ← better dp[5] = 1
dp[6]: coin 1 → dp[5] + 1 = 2
coin 2 → dp[4] + 1 = 3
coin 5 → dp[1] + 1 = 2 dp[6] = 2
Final array: [0, 1, 1, 2, 2, 1, 2]. dp[6] = 2 is not Infinity, so we return 2 — making 6 takes two coins (5 + 1, the path through dp[5]). Notice dp[5] = 1 did the heavy lifting twice: once for itself (a single 5) and again as the cheap remainder when dp[6] spent a 1. That reuse is the entire point of the table.
The contrast with greedy and naive recursion is worth holding onto: greedy would commit to one coin per step and never reconsider; the table tries every coin at every amount but only computes each sub-amount once.
[1, 5, 10, 25] but fails for sets like [1, 3, 4] (where 6 is 3 + 3, not 4 + 1 + 1). Unless you can prove the denomination set is canonical, use DP. When in doubt, DP.dp[0] must be 0, not Infinity. This is the base case the whole table stands on. If you leave dp[0] unreachable, then dp[c] for a coin c computes dp[0] + 1 = Infinity, every cell stays unreachable, and a perfectly solvable input returns -1.-1, not Infinity or 0, when unreachable. A cell that never improved stays Infinity. Map that to -1 on the way out. Returning Infinity leaks an internal sentinel; returning 0 falsely claims "made with zero coins." The amount-0 case is the only legitimate 0.coin <= a before indexing dp[a - coin]. Skip coins larger than the current amount. A coin of 10 can't be the last coin placed toward making 3; without the guard, a - coin is negative and dp[-7] is undefined, poisoning the comparison.Infinity + 1 is still Infinity — lean on it. When dp[a - coin] is unreachable, dp[a - coin] + 1 stays Infinity and never wins the comparison, so unreachable remainders contribute nothing automatically. No special-casing needed; just don't write code that breaks this (e.g. capping at a fixed large integer that can overflow past a real answer).amount + 1, not amount. You need an index for every amount from 0 through amount inclusive. Allocating amount slots drops dp[amount] off the end and reads undefined.from array recording which coin improved each dp[a]. After filling the table, start at amount and repeatedly subtract from[a] until you reach 0, collecting the coins — this reconstructs one optimal combination in O(amount).ways[a] += ways[a - coin], and crucially the coin loop goes outside the amount loop so each denomination is considered once and you count combinations, not ordered sequences. A classic follow-up that looks identical but flips the loop nesting.solve(remaining) result in a Map. Same O(amount × coins) work as the bottom-up table, often more intuitive to write, at the cost of recursion-stack depth on large amounts.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.