Skip to main content

25. Coin Change

mediumAsked at Etsy

Find the fewest coins to make an amount — Etsy's checkout team uses the same DP pattern to compute the minimum number of coupon denominations needed to cover a buyer's order total.

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 needed to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Constraints

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

Examples

Example 1

Input
coins = [1,5,11], amount = 15
Output
3 (5+5+5 or 11+1+1+1+1 — greedy picks 11 first but optimal is 5+5+5)

Example 2

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

Approaches

1. Greedy (incorrect for all inputs)

Always pick the largest coin that fits. Fast but wrong — fails when a mix of smaller coins beats the large coin (e.g., coins=[1,5,11], amount=15: greedy picks 11+1+1+1+1=5 coins; optimal is 5+5+5=3 coins). Include this to show you know greedy doesn't work here.

Time
O(n log n + amount)
Space
O(1)
// WARNING: greedy is WRONG for arbitrary coin sets — shown for contrast
function coinChangeGreedy(coins, amount) {
  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

Build dp[0..amount] where dp[i] = minimum coins to make i. Initialize dp[0]=0 and the rest to Infinity. For each amount from 1 to amount, try each coin: dp[i] = min(dp[i], dp[i-coin]+1). Return dp[amount] or -1 if still 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 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];
}

Tradeoff:

Etsy-specific tips

Etsy interviewers use this to test DP intuition after rejecting greedy. Lead with the greedy counter-example (coins=[1,5,11], amount=15) to show you know why you need DP. Then frame dp[i] as 'the cost to reach amount i from amount 0' — the unbounded-knapsack framing. Expect a follow-up to reconstruct which coins were used, not just the count.

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

Practice these live with InterviewChamp.AI →