Skip to main content

322. Coin Change

mediumAsked at DRW

DRW uses Coin Change to test unbounded knapsack DP — and immediately connects it to tick-size discretization: given a set of valid price increments (tick sizes), what is the minimum number of ticks to express an order quantity? The greedy approach fails for arbitrary denominations; DP is required.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE candidates report Coin Change as a standard medium DP problem in onsite coding rounds, often used to test greedy-vs-DP reasoning.
  • Blind (2025-11)— DRW interview threads note interviewers explicitly ask why greedy fails before accepting the DP solution.

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,6,9], amount = 11
Output
2

Explanation: 5 + 6 = 11. Greedy would pick 9 then fail to complete (2 remaining, needs [1,1] = 3 total). DP finds 2.

Example 2

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

Explanation: No combination reaches 3.

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. For each amount from 1 to target, try all coins and take the minimum. Initialize dp[0] = 0 and all others to 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] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount × |coins|) time and O(amount) space. This is the canonical DP solution. The greedy approach (always take the largest coin ≤ remaining) is incorrect for arbitrary denominations.

DRW-specific tips

DRW interviewers always ask: 'Why does greedy fail here?' Have a concrete counter-example ready: coins = [1, 5, 6, 9], amount = 11. Greedy picks 9, then 1+1 (3 coins). DP finds 5+6 (2 coins). For U.S. coin denominations (1, 5, 10, 25), greedy happens to work — but greedy correctness depends on the denominations satisfying the 'matroid' property. DRW will also ask: 'What if you want to count the number of ways to make the amount?' — that is Coin Change 2 (LC 518), same DP with a sum instead of min.

Common mistakes

  • Initializing dp with 0 instead of Infinity — causes incorrect minimum computation.
  • Not checking dp[i - coin] !== Infinity before adding 1 — Infinity + 1 may overflow in some languages.
  • Using amount + 1 as the 'impossible' sentinel instead of Infinity — works, but less semantically clear.
  • Arguing that greedy works without providing a counter-example — DRW marks this as a gap in reasoning.

Follow-up questions

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

  • Coin Change 2 (LC 518) — count the number of distinct ways to make the amount.
  • Why does greedy work for U.S. coin denominations but not arbitrary denominations?
  • How would you solve Coin Change if the coin supply is limited (each coin can only be used once)?

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 is the inner loop over coins instead of iterating coins in the outer loop?

Iterating amount in the outer loop gives the unbounded knapsack (coins reusable). Iterating coins in the outer loop (0/1 knapsack style) works here too, but the unbounded formulation is more natural for this problem.

What is the time complexity relative to amount?

O(amount × |coins|) — pseudo-polynomial, since 'amount' is an integer value not a length. For amount = 10^4 and |coins| = 12, this is 120,000 operations — trivially fast.

How does this connect to DRW's domain?

Tick-size granularity: given tick sizes [0.01, 0.05, 0.10, 0.25], what is the minimum number of ticks to represent a given price increment? Same DP structure.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →