Skip to main content

322. Coin Change

mediumAsked at Linear

Find the minimum number of coins to make a given amount. Linear asks this as a benchmark DP problem — it separates candidates who pattern-match 'unbounded knapsack' from those who just try greedy and hit the wrong answer.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Frequently cited in Linear SWE onsite reports as a medium DP problem.
  • Blind (2025-11)— Multiple Linear interview threads note Coin Change as a core DP question.

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,10,25], amount = 36
Output
3

Explanation: 25 + 10 + 1 = 36.

Example 2

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

Example 3

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

Approaches

1. Greedy (incorrect in general)

Always pick the largest coin that fits. Works for canonical coin systems but fails on arbitrary denomination sets.

Time
O(n log n)
Space
O(1)
// INCORRECT for arbitrary coin sets — shown to make the greedy-failure point
// Example: coins=[1,3,4], amount=6 → greedy picks 4+1+1=3 coins, but 3+3=2 coins is optimal

Tradeoff: Fails on arbitrary denominations. Only correct for specific canonical sets like US coin denominations. Always pivot to DP.

2. Bottom-up DP (optimal)

Build dp[0..amount] where dp[i] = min coins to make amount i. For each amount, try all coins and take the minimum.

Time
O(amount * n)
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. dp[0] = 0 is the base case; dp[i] = Infinity means unreachable. The recurrence: dp[i] = min over all coins c where c <= i of (dp[i - c] + 1).

Linear-specific tips

Lead with the greedy counterexample: 'Greedy fails on arbitrary denominations — for coins [1,3,4] and amount 6, greedy gives 3 coins but DP finds 2.' Then define the DP state explicitly: 'dp[i] = fewest coins to make exactly i.' Linear interviewers expect you to refute greedy before presenting DP.

Common mistakes

  • Using greedy without checking for counterexamples — greedy is wrong for arbitrary coin sets.
  • Initializing dp with 0 instead of Infinity — then dp[i] is always 0 and you can't detect unreachable amounts.
  • Not returning -1 when dp[amount] remains Infinity — the problem requires -1 for unreachable amounts.

Follow-up questions

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

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

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 DP instead of greedy?

Greedy fails on arbitrary coin denominations. Example: coins=[1,3,4], amount=6. Greedy: 4+1+1=3 coins. DP: 3+3=2 coins. Greedy misses global optima by making locally-best choices.

Why is dp[0] = 0?

Zero coins are needed to make amount 0. This is the base case that anchors all other dp values.

What's the difference between Coin Change and Coin Change 2?

Coin Change asks for the minimum coin count (optimization). Coin Change 2 asks for the number of distinct combinations (counting). Different recurrences — don't conflate them.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →