Skip to main content

20. Coin Change

mediumAsked at Squarespace

Compute the minimum number of coins that make up a target amount; Squarespace uses it to test bottom-up DP versus greedy mistakes.

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

Problem

Given an integer array coins of denominations and an integer amount, return the fewest coins needed to make up that amount. If it cannot be made, return -1. You may reuse 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. Greedy largest-first

Always take the largest coin that fits. Fails on cases like [1, 3, 4] for amount 6.

Time
O(n)
Space
O(1)
coins.sort((a,b)=>b-a);
let n=0,a=amount;
for(const c of coins){ const k=Math.floor(a/c); n+=k; a-=k*c; }
return a===0?n:-1;

Tradeoff:

2. Bottom-up DP over amounts

dp[a] is the fewest coins for amount a; relax dp[a] = min(dp[a], dp[a-c]+1) for each coin c.

Time
O(amount * coins)
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 (a - c >= 0) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Squarespace-specific tips

Squarespace likes when you debunk the greedy attempt up front and link the DP shape to their plan-credit allocation, which fills a balance with the smallest set of credit packs.

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

Practice these live with InterviewChamp.AI →