Skip to main content

322. Coin Change

mediumAsked at Shopify

Shopify uses Coin Change to test unbounded knapsack DP. Real motivation: 'minimum number of coupon denominations to refund this amount'. The interviewer wants you to NOT reach for greedy and to explain why.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Senior Backend onsites include Coin Change as a medium DP round.
  • Reddit r/cscareerquestions (2025-10)— Shopify new-grad reports cite Coin Change with the 'why not greedy' follow-up explicit.

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
3

Explanation: 11 = 5 + 5 + 1.

Example 2

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

Example 3

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

Approaches

1. Greedy (broken — included as anti-pattern)

Sort coins descending; take as many of the largest as possible; recurse on remainder.

Time
O(amount/max)
Space
O(1)
function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (const c of coins) {
    const take = Math.floor(amount / c);
    count += take;
    amount -= take * c;
  }
  return amount === 0 ? count : -1;
}

Tradeoff: Wrong for many inputs. coins = [1,3,4], amount = 6: greedy takes 4+1+1 (3 coins); optimal is 3+3 (2 coins). Useful to demonstrate WHY DP is needed: bring it up, explain the counter-example, then ditch.

2. Top-down DFS + memoization

rec(amount) = 1 + min(rec(amount - c)) for each coin c that fits. Memoize.

Time
O(amount * |coins|)
Space
O(amount)
function coinChangeMemo(coins, amount) {
  const memo = new Array(amount + 1).fill(undefined);
  function rec(rem) {
    if (rem < 0) return -1;
    if (rem === 0) return 0;
    if (memo[rem] !== undefined) return memo[rem];
    let best = Infinity;
    for (const c of coins) {
      const sub = rec(rem - c);
      if (sub >= 0 && sub + 1 < best) best = sub + 1;
    }
    memo[rem] = best === Infinity ? -1 : best;
    return memo[rem];
  }
  return rec(amount);
}

Tradeoff: Cleaner conceptually; same complexity as the bottom-up DP. Recursion depth can be amount = 10^4, which is fine but borderline.

3. Bottom-up DP (canonical optimal)

dp[i] = min coins to make amount i. Start dp[0] = 0, all others = Infinity. For each i, dp[i] = min(dp[i - c] + 1) over all coins c.

Time
O(amount * |coins|)
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 c of coins) {
      if (c <= i && dp[i - c] + 1 < dp[i]) dp[i] = dp[i - c] + 1;
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: Iterative, no recursion. The standard Shopify answer. amount * |coins| = 10^4 * 12 = 1.2 * 10^5 — fast. Subtle: dp[i - c] must already be computed before dp[i], which is naturally true because i increases.

Shopify-specific tips

Shopify wants you to articulate the failure of greedy BEFORE coding. The expected dialogue is: 'I can't use greedy because [1,3,4] for amount 6 shows it fails. I need DP because each subproblem dp[i] is independent and reused.' Then write the bottom-up version. Skipping the greedy-failure explanation is a soft red flag.

Common mistakes

  • Initializing dp values to amount + 1 instead of Infinity — works but reads awkwardly.
  • Returning dp[amount] without the Infinity check — returns Infinity instead of -1 for impossible cases.
  • Iterating coins as the OUTER loop — this is correct for THIS problem but is the wrong structure for the 'count number of ways' variant (LeetCode 518). Be aware of the difference.
  • Forgetting dp[0] = 0 — the empty change is 0 coins.

Follow-up questions

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

  • Coin Change II (LeetCode 518) — count the number of ways, not min coins.
  • What if each coin has a limited supply? (Bounded knapsack, dp[i][j].)
  • Return the actual coin combination, not just the count. (Track back-pointers in dp.)
  • Print all distinct combinations.
  • Online version — amount arrives in a stream, report min for each running total.

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?

Coin denominations don't form a 'canonical' system. With US coins (1, 5, 10, 25), greedy happens to work. With arbitrary denominations like [1, 3, 4], it doesn't. The DP guarantees the optimal answer regardless of denomination structure.

What's the difference between coins as outer vs inner loop?

For min-coins (this problem), order doesn't matter — both work. For count-ways (LeetCode 518), coins MUST be the outer loop, otherwise you'd double-count permutations of the same combination. Common interview gotcha.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →