Skip to main content

25. Coin Change

mediumAsked at Spotify

Find the minimum number of coins to reach a target amount — a bottom-up DP pattern Spotify applies to cost-minimization in dynamic ad-insertion and playlist-segment composition problems.

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

Problem

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 it cannot be made up by any combination of coins, return -1. You may use each coin an unlimited number of times.

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

Explanation: 5 + 5 + 5 = 15.

Example 2

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

Example 3

Input
coins = [1], amount = 0
Output
0

Approaches

1. Recursive with memoisation (top-down DP)

Recurse over remaining amounts; cache results to avoid re-computation. Intuitive entry point for explaining DP.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const memo = new Map();
  const dp = (rem) => {
    if (rem < 0) return -1;
    if (rem === 0) return 0;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) {
      const sub = dp(rem - c);
      if (sub >= 0) best = Math.min(best, sub + 1);
    }
    const result = best === Infinity ? -1 : best;
    memo.set(rem, result);
    return result;
  };
  return dp(amount);
}

Tradeoff:

2. Bottom-up DP (optimal)

Build a dp array from 0 to amount; for each amount, try every coin and keep the minimum. Clean iterative solution with no recursion overhead.

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 (c <= i && dp[i - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Spotify-specific tips

Spotify interviewers use Coin Change to test whether you can articulate the DP recurrence, not just code it. Say explicitly: 'dp[i] = minimum coins to make amount i; I derive it from dp[i - coin] for every valid coin.' They also watch for the Infinity-vs-amount+1 initialization choice — using Infinity is cleaner and worth mentioning why.

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

Practice these live with InterviewChamp.AI →