Skip to main content

322. Coin Change

mediumAsked at Duolingo

Find the minimum number of coins to reach an exact amount — the bottom-up DP pattern that directly models Duolingo's streak-recovery logic, where learners spend XP gems in minimum moves to restore a broken streak to its target length.

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

Problem

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 the amount cannot be reached by any combination of coins, return -1. You have an infinite supply of each coin denomination.

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 = 36
Output
3

Explanation: 25 + 10 + 1 = 36 using 3 coins.

Example 2

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

Example 3

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

Approaches

1. Top-down DP with memoization

Recursively try each coin, memoize the result for each remaining amount.

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 coin of coins) {
      best = Math.min(best, 1 + dp(rem - coin));
    }
    memo.set(rem, best);
    return best;
  }

  const result = dp(amount);
  return result === Infinity ? -1 : result;
}

Tradeoff:

2. Optimal — bottom-up DP

Fill a dp array from 0 to amount; for each sub-amount, try every coin and take the minimum — no recursion stack.

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 coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Duolingo-specific tips

Coin Change maps cleanly onto Duolingo's gem economy: how many streak-shield purchases minimizes cost to hit a target? Interviewers use this problem to see whether you can move from greedy intuition ('always pick the largest coin') to DP after a counterexample like [1, 3, 4], amount 6 (greedy gives 4+1+1=3; DP gives 3+3=2). Always mention the base case dp[0]=0 and the Infinity sentinel before writing code — those two decisions prevent most off-by-one bugs.

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

Practice these live with InterviewChamp.AI →