Skip to main content

22. Coin Change

mediumAsked at Expedia

Find the fewest coins to reach a target amount — Expedia's dynamic-pricing engine applies the same bottom-up DP when assembling minimum-cost fare combinations from discrete price buckets.

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 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,10,25], amount = 30
Output
2

Explanation: 25 + 5 = 30 using 2 coins.

Example 2

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

Approaches

1. Top-down recursion with memoization

For each amount, try every coin and recursively solve the subproblem. Cache 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 -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 !== -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 tabulation

Build a dp array of size amount+1. dp[i] = min coins to make i. Fill left to right using each coin denomination.

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 (i - c >= 0 && dp[i - c] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - c] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Expedia-specific tips

Expedia pricing engineers probe whether you see the unbounded-knapsack structure. Name it. Explain why the recurrence is dp[i] = min over all coins c of dp[i-c]+1 and how that maps to assembling a minimum-component fare from price tiers. The bottom-up variant is preferred in production for its predictable stack depth.

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

Practice these live with InterviewChamp.AI →