Skip to main content

20. Coin Change

mediumAsked at Chime

Compute the fewest number of coins from given denominations that sum to a target amount, or -1 if impossible.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Examples

Example 1

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

Example 2

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

Approaches

1. Greedy by biggest coin

Always take the largest coin not exceeding the remaining amount. Fails when denominations are not canonical.

Time
O(amount)
Space
O(1)
coins.sort((a,b)=>b-a);
let count = 0;
for (const c of coins) {
  while (amount >= c) { amount -= c; count++; }
}
return amount === 0 ? count : -1;

Tradeoff:

2. Bottom-up DP

dp[i] equals the fewest coins needed to make i. Transition: dp[i] = 1 + min over coins c of dp[i - c] when i - c >= 0. Initialize dp[0] = 0 and unreachable values as Infinity.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (i - c >= 0) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Chime-specific tips

Chime asks coin-change to test whether you can model balance-projection sweep amounts as a DP over remaining cents, so reason in cents not floats from the start.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Coin Change and other Chime interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →