Skip to main content

322. Coin Change

mediumAsked at Broadcom

Find the minimum number of coins to make a given amount. Broadcom asks this unbounded-knapsack DP problem because the same 'minimum number of fixed-size units to cover a target' logic appears in packet fragmentation, MTU optimisation, and memory-block allocation in embedded systems.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Cited in Broadcom SWE onsite reports as a standard DP problem in infrastructure software rounds.
  • Blind (2025-10)— Broadcom threads list Coin Change alongside Word Break as core DP problems that test unbounded-knapsack intuition.

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: 11+3*1? No — 5+5+5 = 15 uses 3 coins.

Example 2

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

Explanation: Cannot make 3 with only denomination 2.

Example 3

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

Explanation: Zero coins needed for amount 0.

Approaches

1. Bottom-up DP (unbounded knapsack)

dp[i] = minimum coins to make amount i. Initialise dp[0]=0, rest to Infinity. For each amount i from 1 to amount, try every coin denomination. dp[i] = min(dp[i], dp[i - coin] + 1) if i >= coin and dp[i - coin] != Infinity.

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. Clean bottom-up formulation — easy to trace and verify. This is the standard answer expected at Broadcom.

2. BFS (shortest-path on amount graph)

Model each amount as a node; each coin as an edge of weight 1. BFS from 0 to find the shortest path to 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, head = 0;
  while (head < queue.length) {
    steps++;
    const size = queue.length;
    while (head < size) {
      const curr = queue[head++];
      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: BFS guarantees the shortest path (minimum coins) by level. Equivalent to DP in correctness. Useful to mention as the graph-model alternative — shows breadth of thinking valued at Broadcom.

Broadcom-specific tips

At Broadcom, name the DP variant: 'This is the unbounded knapsack problem — each coin denomination can be used unlimited times.' Connect to domain: 'The same DP recurrence applies to finding the minimum number of fixed-size memory pages to satisfy an allocation request.' Proactively walk through the edge case amount=0 returns 0 and when no valid combination exists returns -1 (dp[amount] = Infinity).

Common mistakes

  • Initialising dp with 0 instead of Infinity — causes incorrect minimums because every amount appears achievable.
  • Not initialising dp[0] = 0 — the base case is essential.
  • Returning dp[amount] directly when it equals Infinity instead of returning -1.
  • Greedy approach: greedily taking the largest coin fails (e.g., coins=[1,5,11], amount=15: greedy gives 11+1+1+1+1 = 5 coins, but 5+5+5 = 3 coins is optimal).

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of distinct combinations, not the minimum.
  • How would you reconstruct the actual coin sequence used, not just the minimum count?
  • What if coin denominations change dynamically and you must answer queries online?

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 for Coin Change?

Greedy works only when coin denominations are canonical (e.g., standard US currency). Arbitrary denominations can have counterexamples — always use DP.

What is the 'unbounded' in unbounded knapsack?

Each item (coin) can be selected an unlimited number of times. This contrasts with 0/1 knapsack where each item is used at most once.

Why is BFS equivalent to DP here?

BFS finds the shortest path in an unweighted graph. If you model each integer amount as a node and each coin denomination as an edge, the minimum coins to reach amount is the BFS depth — identical to the DP solution.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →