Skip to main content

322. Coin Change

mediumAsked at Hugging Face

Find the minimum number of coins to make a target amount. Hugging Face uses this unbounded knapsack DP to assess whether candidates can formulate and optimize a recurrence — the same skill needed to tune beam search width or minimize inference steps in iterative decoding strategies.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2025-12)— Listed in Hugging Face SWE onsite feedback as a classic DP problem for optimizing under constraints.
  • Blind (2025-10)— Hugging Face interview threads cite Coin Change as a medium DP problem with a clean recurrence structure.

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. Three coins.

Example 2

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

Explanation: Cannot make 3 with only 2s.

Example 3

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

Explanation: Zero coins needed for amount 0.

Approaches

1. Bottom-up DP (tabulation)

dp[i] = minimum coins to make amount i. Initialize dp[0] = 0, all others = Infinity. For each amount from 1 to amount, try all coins: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin <= i.

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

Tradeoff: O(amount * n) time, O(amount) space. This is the canonical DP answer. The inner loop order (amount outer, coin inner) makes it an unbounded knapsack — each coin can be used multiple times.

2. BFS (shortest path analogy)

Treat each amount as a graph node with edges to amount - coin. BFS from 0 finds the shortest path to the target amount, where path length = number of coins.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  if (amount === 0) return 0;
  const visited = new Set([0]);
  const queue = [0];
  let steps = 0;
  while (queue.length) {
    steps++;
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const curr = queue.shift();
      for (const coin of coins) {
        const next = curr + coin;
        if (next === amount) return steps;
        if (next < amount && !visited.has(next)) {
          visited.add(next);
          queue.push(next);
        }
      }
    }
  }
  return -1;
}

Tradeoff: Same asymptotic complexity, but BFS has higher constant overhead due to queue operations. Useful to mention as an alternative framing — 'this is a shortest-path problem on an unweighted graph' — but DP is preferred in practice.

Hugging Face-specific tips

Hugging Face will ask: 'Why doesn't greedy work here?' Coin Change is a classic greedy counterexample — coins = [1, 3, 4], amount = 6: greedy picks 4+1+1 = 3 coins; DP finds 3+3 = 2 coins. Explain this concisely. Then connect DP to ML: 'Minimizing inference steps in iterative generation uses the same recurrence logic — finding the minimum number of decoding steps to reach a target output quality given a set of allowed step sizes.'

Common mistakes

  • Using greedy — doesn't work for arbitrary coin sets (only for specific cases like standard denominations).
  • Initializing dp with -1 instead of Infinity — -1 is the sentinel for 'unreachable', which interferes with the min comparison.
  • Forgetting to check coin <= i before accessing dp[i - coin] — prevents negative index access.
  • Confusing bounded knapsack (each coin used once) with unbounded (each coin used any number of times).

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Coin Change II (LC 518) — count the number of combinations to make the amount.
  • Perfect Squares (LC 279) — same DP structure, coins are perfect squares.
  • How would you solve this if each coin denomination had a limited supply?

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 is the outer loop over amount and inner over coins?

This gives the unbounded knapsack structure where each coin can be reused any number of times. If the loops were swapped and each coin processed once, you'd get the 0/1 knapsack (each coin used at most once).

Why initialize dp to Infinity and not -1?

The recurrence uses Math.min(), so the initial value must be larger than any valid answer. Infinity serves as 'unreachable'. -1 would cause Math.min(-1, dp[i-coin]+1) = -1, corrupting the DP table.

Is greedy ever correct for coin change?

Yes — for canonical coin systems (1¢, 5¢, 10¢, 25¢) greedy is provably optimal. For arbitrary coin sets it's not. The DP solution is always correct regardless of coin values.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →