Skip to main content

322. Coin Change

mediumAsked at Glean

Glean uses Coin Change to assess unbounded-knapsack DP thinking — a pattern directly analogous to finding the minimum number of query re-expansions needed to cover a target relevance budget.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2025-11)— Cited in Glean onsite prep notes as a classic DP problem appearing in later coding rounds.
  • Blind (2025-08)— Glean SWE threads recommend Coin Change as a must-prepare medium representing the unbounded knapsack category.

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: 15 = 5+5+5 (three 5-coins). 11+1+1+1+1 = 4 coins — not optimal.

Example 2

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

Explanation: No combination of even-denomination coins can sum to 3.

Example 3

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

Explanation: Zero amount needs zero coins.

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 target, try each coin: dp[i] = min(dp[i], dp[i - coin] + 1).

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 definitive answer. The Infinity sentinel cleanly represents unreachable amounts.

2. BFS (level = number of coins)

Treat the problem as a shortest-path problem in an unweighted graph where each node is an amount and edges are coin denominations. BFS finds the minimum number of edges (coins) to reach amount from 0.

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

Tradeoff: Also O(amount * n). BFS naturally gives the minimum path (fewest coins). Useful to mention as an alternative perspective — every layer of BFS adds one more coin.

Glean-specific tips

State the recurrence before any code: 'dp[i] = minimum coins to form amount i. For each coin, if I used it last, I need dp[i - coin] + 1 coins.' Glean interviewers appreciate explicit recurrence articulation. Note that greedy (always pick the largest coin) fails on inputs like [1,5,11] for amount=15 — a greedy algorithm would pick 11 first, leaving 4 and needing four 1-coins for a total of 5, while three 5-coins is optimal.

Common mistakes

  • Using greedy (pick largest coin first) — fails for non-canonical coin systems like [1,5,11].
  • Initializing dp to 0 instead of Infinity — valid amounts would be overwritten; only dp[0] = 0 is a valid base case.
  • Forgetting to check dp[i - coin] !== Infinity before using it — Infinity + 1 in JavaScript is still Infinity, so it works numerically, but it's good practice to check.
  • Returning dp[amount] directly without converting Infinity to -1 — the problem requires -1 for impossible amounts.

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of distinct ways to make amount, not the minimum coins.
  • What if each coin denomination can only be used once? (0/1 knapsack variant)
  • Perfect Squares (LC 279) — same DP pattern with squares as denominations.

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

Greedy works only for canonical coin systems (like US currency). For coins = [1,5,11], greedy picks 11 for amount 15, leaving 4 ones — 5 coins total. The optimal is three 5-coins. DP considers all possibilities.

Is this 0/1 knapsack or unbounded knapsack?

Unbounded knapsack — each coin denomination can be used any number of times. In 0/1 knapsack each item can only be used once, which changes the DP loop order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →