Skip to main content

21. Coin Change

mediumAsked at Booking

Find the fewest coins to reach an exact total — Booking's pricing engine uses the same unbounded DP when breaking a nightly rate into fee denominations or computing minimum discount combinations to hit a target price.

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 no combination can reach the amount, 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 (three coins).

Example 2

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

Example 3

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

Approaches

1. Recursive with memoization (top-down)

Try every coin at each amount recursively; cache sub-results to avoid recomputation.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const memo = new Map();

  function dp(rem) {
    if (rem === 0) return 0;
    if (rem < 0) return -1;
    if (memo.has(rem)) return memo.get(rem);

    let best = Infinity;
    for (const c of coins) {
      const sub = dp(rem - c);
      if (sub !== -1) 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

Build dp[0..amount] iteratively. dp[i] = min coins to reach i. Fill left to right using each coin.

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:

Booking-specific tips

Booking prices in 40+ currencies with custom fee structures. They want to see you recognize unbounded knapsack vs 0/1 knapsack immediately. Always initialize the DP array with Infinity (not -1) and convert at the end — mixing sentinel values is a common bug they screen for.

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

Practice these live with InterviewChamp.AI →