322. Coin Change

Q: Why doesn't greedy work for coin change?

Greedy works only for canonical coin systems (like US coins). For arbitrary denominations (e.g., [1,3,4]), always choosing the largest coin can miss a more efficient combination.

Q: Why initialise to Infinity instead of a large number like amount+1?

Infinity is semantically correct and avoids magic numbers. amount+1 also works since it's guaranteed to be larger than any valid answer.

Q: What is the space optimisation possible here?

The 1D dp array is already the space-optimised version. A 2D approach (over coins × amounts) would use O(n × amount) space — less efficient.

mediumAsked at Gusto

Find the minimum number of coins needed to make up an amount. Gusto's payroll and benefits domain makes this a grounded problem — think minimum transaction splits for expense reimbursement. They want bottom-up DP with a clear recurrence, not naive recursion.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

Glassdoor (2026-Q1)— Reported as a Gusto medium DP problem used in onsite rounds to test bottom-up tabulation.
Blind (2025-11)— Gusto SWE threads cite Coin Change as a reliable DP problem that appears across multiple interview levels.

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

Explanation: 11 = 5 + 5 + 1 (three coins).

Example 2

Input

coins = [2], amount = 3

Output

-1

Explanation: 3 cannot be made with only coin denomination 2.

Example 3

Input

coins = [1], amount = 0

Output

Explanation: Zero amount requires zero coins.

Approaches

1. Bottom-up DP (tabulation)

dp[i] = minimum coins to make amount i. Initialise dp[0] = 0 and everything else to Infinity. For each amount from 1 to amount, try every 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 canonical answer. Clear recurrence: the minimum coins for amount i is one more than the minimum for amount i−coin, for the best coin choice.

2. Top-down memoised recursion

Recursively compute the minimum coins for each amount. Cache results to avoid recomputation.

Time: O(amount × coins.length)
Space: O(amount)

function coinChange(coins, amount) {
  const memo = new Map();
  function minCoins(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining);
    let best = Infinity;
    for (const coin of coins) {
      const result = minCoins(remaining - coin);
      if (result !== Infinity) best = Math.min(best, result + 1);
    }
    memo.set(remaining, best);
    return best;
  }
  const result = minCoins(amount);
  return result === Infinity ? -1 : result;
}

Tradeoff: Same complexity as bottom-up but uses the call stack. Easier for some candidates to derive. Watch for stack depth — amount up to 10^4 is safe in JS.

Gusto-specific tips

State the recurrence before coding: 'dp[i] = 1 + min over all coins of dp[i - coin], for all coins where coin ≤ i.' Initialise dp to Infinity (not -1 or 0) so that min comparisons work correctly. Gusto interviewers like the follow-up: 'Why can't greedy work here?' — the answer is that coins may not be canonical (e.g., [1,3,4], amount=6: greedy gives 4+1+1=3 coins, but 3+3=2 coins is optimal).

Common mistakes

Initialising dp to -1 instead of Infinity — min comparisons with -1 produce wrong results.
Forgetting the dp[0] = 0 base case — without it, no amount can ever be computed.
Using greedy (always pick the largest coin) — incorrect when coin denominations aren't canonical.
Not checking dp[i - coin] !== Infinity before taking dp[i - coin] + 1 — 1 + Infinity overflows in some languages.

Follow-up questions

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

Coin Change 2 (LC 518) — count the number of combinations that make up the amount.
What if each coin can only be used once? (0/1 knapsack variant.)
How would you reconstruct which coins were used to achieve the minimum?

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 coins). For arbitrary denominations (e.g., [1,3,4]), always choosing the largest coin can miss a more efficient combination.

Why initialise to Infinity instead of a large number like amount+1?

Infinity is semantically correct and avoids magic numbers. amount+1 also works since it's guaranteed to be larger than any valid answer.

What is the space optimisation possible here?

The 1D dp array is already the space-optimised version. A 2D approach (over coins × amounts) would use O(n × amount) space — less efficient.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →