Skip to main content

322. Coin Change

mediumAsked at IBM

Coin Change is IBM's unbounded-knapsack DP screener. The interviewer is grading whether you recognize the unbounded variant (each coin reusable), whether you ship the O(amount * coins) bottom-up DP, and whether you handle the impossible case (amount > 0 but no combination works) cleanly.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 onsite recurring DP problem.
  • LeetCode (2026-Q1)— Top-25 IBM-tagged problem (medium tier).
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive with DP variants.

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,2,5], amount = 11
Output
3

Explanation: 11 = 5 + 5 + 1

Example 2

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

Example 3

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

Approaches

1. Greedy (wrong — for context only)

Repeatedly pick the largest coin not exceeding remaining amount.

Time
O(amount)
Space
O(1)
function coinChangeGreedy(coins, amount) {
  // INCORRECT in general — only works for canonical coin systems
  const sorted = [...coins].sort((a, b) => b - a);
  let count = 0;
  for (const c of sorted) {
    while (amount >= c) {
      amount -= c;
      count++;
    }
  }
  return amount === 0 ? count : -1;
}

Tradeoff: Disqualified — fails on non-canonical coin systems (e.g., coins=[1,3,4], amount=6 → greedy gives 4+1+1=3 coins; optimal is 3+3=2). Mention greedy ONLY to dismiss it as the canonical wrong answer.

2. Top-down DP with memo

Recurse: minCoins(rem) = 1 + min over coins of minCoins(rem - coin). Memoize by remaining amount.

Time
O(amount * coins)
Space
O(amount)
function coinChangeMemo(coins, amount) {
  const memo = new Map();
  const solve = (rem) => {
    if (rem < 0) return Infinity;
    if (rem === 0) return 0;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) {
      const sub = solve(rem - c);
      if (sub + 1 < best) best = sub + 1;
    }
    memo.set(rem, best);
    return best;
  };
  const ans = solve(amount);
  return ans === Infinity ? -1 : ans;
}

Tradeoff: Cleaner derivation from the recurrence. Uses O(amount) recursion-stack depth which could overflow at amount = 10^4 — bottom-up is preferred for that reason.

3. Bottom-up DP (optimal)

dp[i] = min coins to make i. dp[0] = 0; dp[i] = min over coins of dp[i - coin] + 1.

Time
O(amount * coins)
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 - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount * coins) time and O(amount) space — the canonical answer. Using Infinity as the sentinel (instead of -1 or amount+1) makes the comparison clean: any real path is finite, so any Infinity means impossible.

IBM-specific tips

IBM specifically tests whether you avoid the greedy trap on this problem. Always state 'greedy doesn't work for arbitrary coin systems — e.g., [1,3,4] with target 6 gives 4+1+1 greedy vs 3+3 optimal' before coding the DP. That sentence is the rubric checkbox; jumping straight to DP without naming the trap reads as memorized. Use Infinity (not -1 or amount+1) as the sentinel for cleaner min-comparison.

Common mistakes

  • Using greedy and shipping the wrong answer.
  • Initializing dp[0] = Infinity instead of 0 — DP never finds a valid path.
  • Returning dp[amount] without the Infinity check — returns a huge number for impossible amounts.
  • Looping inner over `i` then outer over coins — same result but harder to reason about. The outer-amount, inner-coins order is the conventional one.
  • Using -1 as the impossibility sentinel and then doing `dp[i-c] + 1` — propagates 0 instead of impossibility.

Follow-up questions

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

  • Coin Change II — count the number of combinations summing to amount (LeetCode 518).
  • What if each coin can only be used once? (0/1 knapsack — different DP structure.)
  • Return the actual coin sequence, not just the count.
  • What if coin denominations are huge (10^9) and amount is small? (BFS on the amount graph.)

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 doesn't greedy work?

Because non-canonical coin systems can have local optima that aren't globally optimal. Example: coins=[1,3,4], amount=6. Greedy picks 4 first, leaves 2, then 1+1 — 3 coins total. But 3+3 = 2 coins. The DP explores all options; greedy commits early and gets stuck.

When IS greedy correct for coin problems?

For 'canonical' coin systems where the denominations form a matroid-like structure — US coins (1, 5, 10, 25), most national currencies. The mathematical condition is that the system is 'greedy-friendly,' which is non-trivial to check. Safer to always use DP for the LeetCode version where coins are arbitrary.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →