Skip to main content

28. Coin Change

mediumAsked at Doordash

Find the fewest coins to reach an exact amount — Doordash uses this DP pattern for delivery batch optimization: the minimum number of courier trips to fulfill an order backlog of a given volume.

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 that amount cannot be made up by any combination of coins, return -1. You may use each coin denomination 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: Greedy picks 11+1+1+1+1=5 coins. DP finds 5+5+5=3 coins — greedy fails here.

Example 2

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

Approaches

1. Top-down DP with memoization

Recursively try each coin; memoize the minimum coins needed for each sub-amount to avoid redundant work.

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 Infinity;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) {
      best = Math.min(best, 1 + dp(rem - c));
    }
    memo.set(rem, best);
    return best;
  }
  const result = dp(amount);
  return result === Infinity ? -1 : result;
}

Tradeoff:

2. Bottom-up DP (unbounded knapsack)

Build a dp array where dp[i] = min coins for amount i. Initialize dp[0]=0, all others Infinity. For each amount from 1 to target, try every 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 a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] + 1 < dp[a]) {
        dp[a] = dp[a - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Doordash-specific tips

Doordash surfaces this as a batching problem: 'given batch sizes [1, 5, 11] orders per trip, what's the fewest trips for 15 orders?' — and greedy fails (greedy picks 11+1+1+1+1=5 trips, DP finds 5+5+5=3). That counter-example is exactly what interviewers want you to surface proactively. Show the greedy failure before writing DP. Follow-ups: count the number of ways to make change (combinatorics variant), and the 2D variant with item weights.

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

Practice these live with InterviewChamp.AI →