322. Coin Change

Q: Why iterate over amounts in the outer loop instead of coins?

This is an unbounded knapsack — each coin can be used unlimited times. Iterating over amounts means each amount builds on all previously computed states, naturally allowing coin reuse.

Q: What if amount is 0?

dp[0] = 0. Zero coins are needed to make amount 0. The function returns 0, which is correct.

mediumAsked at AMD

Find the minimum number of coins to make a given amount. AMD uses this unbounded-knapsack DP to test state-space minimization thinking — the same 'minimum cost to reach a target state' pattern arises in GPU instruction scheduling, power-state transitions, and DVFS (dynamic voltage and frequency scaling) optimization.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in AMD loops.

Glassdoor (2026-Q1)— AMD SWE candidates report Coin Change as a typical bottom-up DP medium in second coding rounds.
Blind (2025-10)— AMD interview prep threads list Coin Change as a canonical DP problem, with AMD follow-ups on minimizing hardware power transitions.

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,25], amount = 30

Output

Explanation: Two 15-cent coins... actually 25 + 5 = 30, 2 coins.

Example 2

Input

coins = [2], amount = 3

Output

-1

Explanation: Cannot reach 3 with only 2-denomination coins.

Example 3

Input

coins = [1], amount = 0

Output

Explanation: Zero coins needed for amount 0.

Approaches

1. Bottom-up DP

dp[i] = minimum coins to make amount i. Initialize dp[0]=0 and all others to Infinity. For each amount from 1 to amount, try every coin and take the minimum.

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: O(amount * n) time, O(amount) space. The unbounded knapsack structure allows reusing coins, which is why we process each amount once and try all coins (not a 0-1 knapsack).

2. BFS (shortest path in an unweighted graph)

Model each amount as a node. Each coin is an edge of weight 1. BFS from 0 finds the shortest path (fewest coins) to reach amount.

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[i];
      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);
        }
      }
    }
    queue.splice(0, size);
  }
  return -1;
}

Tradeoff: Same complexity as DP. BFS guarantees the first time you reach amount you've found the minimum. Useful framing for AMD's graph-scheduling context, but DP is more conventional for this problem.

AMD-specific tips

Frame this as a state-machine minimization problem — each amount is a state, each coin is a state transition of cost 1. The minimum-cost path from state 0 to state 'amount' is the answer. AMD power-management engineers solve identical problems: what is the minimum number of DVFS frequency transitions to move from idle to a target compute state? The DP recurrence maps directly. Mention initializing with Infinity (not -1 or 0) to avoid conflating 'unreachable' with 'zero coins needed'.

Common mistakes

Initializing dp with -1 instead of Infinity — -1 is the return code for 'impossible', not a valid intermediate sentinel.
Forgetting dp[0] = 0 — the base case is zero coins needed for amount 0.
Using coins.length as the outer loop — iterate over amounts, not coin indices (unbounded knapsack).
Not checking dp[i - coin] !== Infinity before adding 1 — Infinity + 1 wraps or stays Infinity depending on JS behavior.

Follow-up questions

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

Coin Change 2 (LC 518) — count the number of ways to make the amount (not minimum coins).
Perfect Squares (LC 279) — same DP structure with coins = perfect squares.
How does this relate to minimum transition cost in a power-state machine?

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 iterate over amounts in the outer loop instead of coins?

This is an unbounded knapsack — each coin can be used unlimited times. Iterating over amounts means each amount builds on all previously computed states, naturally allowing coin reuse.

What if amount is 0?

dp[0] = 0. Zero coins are needed to make amount 0. The function returns 0, which is correct.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →