medium

Coin Change

Find the fewest coins needed to make up a given amount from a set of coin values.

1. Define the problem

Coin Change

You are given an integer array coins representing coin denominations and an integer amount. Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1. The fewest coins for amount i is 1 plus the fewest coins already found for amount i minus a coin's value , tried for every coin and keeping the smallest result — a classic bottom-up table built from amount 0 up to the target.

Constraints

  • 1 ≤ coins.length ≤ 12
  • 1 ≤ coinsi ≤ 231 - 1
  • 0 ≤ amount ≤ 104

Example

Inputcoins = [1, 2, 5], amount = 11
Output3

Explanation 11 = 5 + 5 + 1, using 3 coins — no combination uses fewer.

2. Know the words first

In plain terms

Denomination
One of the fixed coin values you are allowed to use, like 1, 2, or 5.
3. Visualize the solution

Fill the fewest-coins table from amount 0 up to the target

Fill the fewest-coins table from amount 0 up to the target
Statusbase

One cell per amount from 0 to 5. Only dp[0] = 0 is known — zero coins are needed to make amount 0.

What happens in this step

coins = [1, 2, 5]
dp[0] = 0

The base case: making amount 0 requires no coins at all. Amounts 1 to 5 are still blank.
Step 1 of 6

Steps to visualize

  1. Set dp0 = 0 — it takes zero coins to make amount zero.
  2. For every amount from 1 upward, try every coin no larger than the amount.
  3. dpamount = 1 + the smallest dp[amount - coin] found across all usable coins.
  4. The value at dpamount is the answer, or -1 if it was never reached.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill the fewest-coins table from amount 0 up to the target
Statusbase

One cell per amount from 0 to 5. Only dp[0] = 0 is known — zero coins are needed to make amount 0.

What happens in this step

coins = [1, 2, 5]
dp[0] = 0

The base case: making amount 0 requires no coins at all. Amounts 1 to 5 are still blank.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1;
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}
Time
O(amount * coins.length)
Space
O(amount)
6. Test cases

Test cases

InputExpectedCovers
coins = [1, 2, 5], amount = 113example from the docstring
coins = [2], amount = 3-1amount cannot be made with the given coins
coins = [1], amount = 00smallest valid amount, no coins needed
coins = [3], amount = 93a single coin denomination that divides evenly
coins = [5], amount = 3-1every coin is larger than the target amount
coins = [7], amount = 71amount exactly equals one coin
coins = [1, 2, 5], amount = 10020a larger amount solved entirely with the biggest coin

Keep reading