Skip to main content

23. Coin Change

mediumAsked at Instacart

Find the minimum number of coins that sum to an amount — Instacart draws on this classic DP pattern when computing the fewest batch trips a shopper should make to cover a list of item weights optimally.

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 that you need 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,11], amount = 15
Output
3

Explanation: 11 + 1 + 1 + 1 + 1 = 15 uses 5 coins; 5 + 5 + 5 = 15 uses 3 coins.

Example 2

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

Approaches

1. Top-down memoized recursion

For each remaining amount, try each coin denomination and recurse. Cache sub-problem results.

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 >= 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

Build dp[0..amount] where dp[i] = min coins to make i. Seed dp[0] = 0; for each amount from 1 to target, try 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] = Math.min(dp[i], dp[i - c] + 1);
    }
  }

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

Tradeoff:

Instacart-specific tips

Instacart often frames this as a batch-dispatch problem: given a set of container sizes, what is the minimum number of containers to ship exactly N items? The bottom-up table is what the interviewer expects, and they'll probe the unbounded knapsack intuition — why you loop amounts in the outer loop and coins in the inner loop versus the 0/1 knapsack transposition.

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

Practice these live with InterviewChamp.AI →