Coin Change Problem

Medium

Problem

Given coin denominations (unlimited supply) and an amount, return the fewest coins that make up the amount, or −1 if it cannot be made. Coin Change II asks instead for the number of distinct combinations.

Example 1

Input:  coins = [1, 2, 5], amount = 11
Output: 3

5 + 5 + 1.

Example 2

Input:  coins = [2], amount = 3
Output: -1

Also asked as: coin change · minimum number of coins

Test cases

Case 1

Input:    [1,2,5], 11
Expected: 3

Case 2

Input:    [2], 3
Expected: -1

Case 3

Input:    [1], 0
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Bottom-up (min coins for each amount)

Time O(amount · coins)Space O(amount)

dp[a] = 1 + min over coins c≤a of dp[a−c]. Unbounded knapsack shape.

function coinChange(coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++)
for (const c of coins)
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] === Infinity ? -1 : dp[amount];
}

2. Count the number of ways

Time O(amount · coins)Space O(amount)

Different question, same table: iterate coins in the outer loop so combinations aren’t double-counted.

function changeWays(coins, amount) {
const dp = Array(amount + 1).fill(0);
dp[0] = 1;
for (const c of coins)
for (let a = c; a <= amount; a++)
dp[a] += dp[a - c];
return dp[amount];
}