Skip to main content

22. Coin Change

mediumAsked at Klarna

Find the fewest coins needed to make a target amount, or -1 if impossible.

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

Problem

You are given an integer array coins representing coin denominations and an integer amount representing a total amount. Return the fewest number of coins needed to make up that amount, or -1 if the amount cannot be made up by any combination of coins.

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. Naive recursion

Try every coin choice recursively; take the min coin count returned.

Time
O(coins^amount)
Space
O(amount)
function coinChange(coins, amount) {
  const go = (a) => {
    if (a === 0) return 0;
    if (a < 0) return Infinity;
    let best = Infinity;
    for (const c of coins) best = Math.min(best, 1 + go(a - c));
    return best;
  };
  const r = go(amount);
  return r === Infinity ? -1 : r;
}

Tradeoff:

2. Bottom-up DP

Build dp[a] = min coins for amount a by extending each smaller amount with each available coin. One pass over (amount * coins).

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 a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Klarna-specific tips

Klarna's BNPL installment-ledger team uses this exact DP shape to split a balance into the fewest installments at allowed denominations; they care most about whether you correctly mark unreachable amounts as -1.

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 Klarna interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →