Skip to main content

322. Coin Change

mediumAsked at Citadel

Coin Change is the canonical unbounded knapsack problem and a gateway to understanding DP on finite targets. At Citadel, structurally identical problems appear in portfolio replication (can you replicate a target payout using a minimum number of instruments?). The interview tests whether you define the DP state precisely and initialize correctly.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2026-Q1)— Citadel SWE candidates list Coin Change as a recurring DP benchmark in coding assessments, often followed by harder DP variants.
  • Blind (2025-10)— Citadel SWE threads confirm Coin Change is used to probe unbounded DP mastery — candidates who use recursion without memoization are immediately flagged.

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 assume that you have an infinite number of each kind of coin.

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, 3 coins. Note: greedy (11 + 1 + 1 + 1 + 1) gives 5 coins — worse.

Example 2

Input
coins = [1,2,5], amount = 11
Output
3

Explanation: 5 + 5 + 1 = 11.

Example 3

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

Explanation: Cannot make 3 with only denomination 2.

Approaches

1. Bottom-up DP

dp[i] = minimum coins to make amount i. For each amount from 1 to target, try each coin denomination. dp[i] = min(dp[i], dp[i - coin] + 1) for all valid coins.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 coins needed to make amount 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: O(amount * |coins|) time, O(amount) space. Bottom-up avoids recursion overhead. Initializing with Infinity and returning -1 when dp[amount] is still Infinity handles the unreachable case cleanly.

2. Top-down memoization

Recursively compute the minimum coins for each subamount, memoizing results. More natural to write but uses O(amount) call stack.

Time
O(amount * coins.length)
Space
O(amount) memo + call stack
function coinChange(coins, amount) {
  const memo = new Map();
  function dp(rem) {
    if (rem < 0) return Infinity;
    if (rem === 0) return 0;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const coin of coins) {
      const sub = dp(rem - coin);
      if (sub !== Infinity) best = Math.min(best, sub + 1);
    }
    memo.set(rem, best);
    return best;
  }
  const result = dp(amount);
  return result === Infinity ? -1 : result;
}

Tradeoff: Same asymptotic complexity as bottom-up. More natural for candidates who think recursively. The memo Map adds overhead per entry versus the array in the bottom-up approach — bottom-up is preferred for performance.

Citadel-specific tips

Before coding, state explicitly why greedy fails: coins = [1, 5, 11], amount = 15 — greedy picks 11+1+1+1+1 = 5 coins, but optimal is 5+5+5 = 3 coins. Greedy only works when coin denominations form a canonical system (like US coins). Citadel interviewers specifically probe greedy vs DP judgment — saying 'greedy works here' without qualification is a red flag. After coding, verify: what if amount = 0? (Return 0.) What if coins contains amount exactly? (Return 1.)

Common mistakes

  • Initializing dp[0] to 0 but forgetting Infinity for all other positions — causes incorrect minimum comparisons.
  • Using amount + 1 as the unreachable sentinel instead of Infinity — this works but is non-idiomatic and confusing when coins[i] = 1 and amount is large.
  • Not checking coin <= i before accessing dp[i - coin] — array index underflow when coin > i.
  • Using greedy (sort and pick largest coin first) — fails for non-canonical denomination sets.

Follow-up questions

An interviewer at Citadel may pivot to one of these next:

  • Coin Change 2 (LC 518) — count the number of combinations (not minimum coins).
  • Perfect Squares (LC 279) — same DP pattern with coins = [1, 4, 9, 16, ...].
  • What if each coin denomination has a limited supply (bounded knapsack)?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does greedy fail on some coin sets?

Greedy assumes taking the largest denomination always leads to a global optimum. This holds for standard currencies (US, EU) because their denominations are designed to form a canonical system. For arbitrary denominations, the greedy choice at one step can block the optimal choice later.

Is the DP order (inner loop over coins vs outer loop over coins) interchangeable?

Yes — for this unbounded problem (infinite coins), both orderings give the same result. The outer-amount / inner-coin order is more natural. Coin Change 2 requires a specific ordering to count distinct combinations.

What is the time complexity for the given constraints (amount ≤ 10^4, coins.length ≤ 12)?

O(10^4 * 12) = O(120,000) — negligible. The DP is very fast in practice.

Practice these live with InterviewChamp.AI

Drill Coin Change and other Citadel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →