Skip to main content

322. Coin Change

mediumAsked at Apple

Coin Change is Apple's go-to unbounded-knapsack DP medium. dp[i] = min coins to make amount i. For each i, try every coin and take the minimum. Apple is grading whether you can write the recurrence AND explain why the greedy (take the largest coin) does not work on arbitrary denominations.

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

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list Coin Change as a recurring 30-minute DP medium.
  • Blind (2025-12)— Apple ICT3/ICT4 reports cite Coin Change with the 'why not greedy?' verbal 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,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. Bottom-up DP (optimal)

dp[i] = min coins to make amount i. Initialize dp[0] = 0 and dp[i] = Infinity for i > 0. For each amount i, try every coin c <= i: dp[i] = min(dp[i], dp[i-c] + 1).

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] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - c] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount * |coins|) — for the constraints (amount <= 10^4, coins <= 12), 120K operations, fast. The Infinity sentinel makes the comparison clean; the final check converts unreachable amounts to -1.

2. Top-down memoized DFS

solve(remaining): if 0 return 0, if < 0 return Infinity. Try each coin, recurse on remaining - coin, take min + 1. Memoize on remaining.

Time
O(amount * |coins|)
Space
O(amount)
function coinChange(coins, amount) {
  const memo = new Map();
  function solve(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining);
    let best = Infinity;
    for (const c of coins) {
      const sub = solve(remaining - c);
      if (sub !== Infinity) best = Math.min(best, sub + 1);
    }
    memo.set(remaining, best);
    return best;
  }
  const result = solve(amount);
  return result === Infinity ? -1 : result;
}

Tradeoff: Same complexity. Apple accepts either; bottom-up is preferred because the table is inspectable and there's no recursion-depth concern at amount=10^4.

3. Greedy (rejected for general coins)

Always take the largest coin <= remaining.

Time
O(amount / max_coin)
Space
O(1)
// Reject: coins=[1,3,4], amount=6.
// Greedy: 4 + 1 + 1 = 3 coins.
// Optimal: 3 + 3 = 2 coins.

Tradeoff: Works for the US coin system (1, 5, 10, 25) but fails on arbitrary denominations. Apple explicitly asks 'why not greedy?' — your answer is the [1,3,4] counter-example above.

Apple-specific tips

Apple is grading two things: (1) the DP recurrence, and (2) why greedy doesn't work. Have the counter-example coins=[1,3,4], amount=6 memorized. Say: 'greedy would take 4+1+1=3 coins; optimal is 3+3=2. Greedy fails because the coin set isn't canonical. DP works because it considers every coin at every state.' That two-sentence answer earns full credit on the 'why not greedy' question.

Common mistakes

  • Using -1 as the unreachable sentinel and then comparing to -1 inside the min — produces wrong answers when dp[i-c] is -1.
  • Looping coins outside instead of amount outside — both work but the standard form is amount-outside for the 'min coins' variant.
  • Returning Infinity directly instead of converting to -1.

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of ways, not the min count.
  • Combination Sum IV (LC 377) — count ordered combinations.
  • Perfect Squares (LC 279) — same DP shape with squares as the 'coins.'

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 not greedy?

Greedy assumes the largest coin <= remaining is always part of the optimal answer. Counter-example: coins=[1,3,4], amount=6. Greedy gives 4+1+1=3; optimal is 3+3=2.

Why Infinity and not -1 as the sentinel?

Because Math.min(Infinity, dp[i-c] + 1) works directly when dp[i-c] is a valid number; the case where dp[i-c] is Infinity also propagates correctly. Using -1 forces extra branching.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →