p57 — Coin Change

Source: LeetCode 322 · Medium · Topics: Unbounded Knapsack, 1D DP Companies (2024–2025): Amazon (very high), Google (high), Meta (high), Microsoft (high), Bloomberg (high), Stripe (medium-high) Loop position: The canonical “first hard DP.” Tests whether you handle “no solution” returns, derive unbounded recurrence cleanly, and reject the seductive-but-wrong greedy.

1. Quick Context

Given coin denominations coins[] (positive ints, no duplicates) and amount, return the minimum number of coins summing to amount, or -1 if impossible. Coins can be used unlimited times.

Classic unbounded knapsack:

dp[a] = min(dp[a - c] + 1) over all coins c where c <= a
dp[0] = 0
answer = dp[amount] if dp[amount] != INF else -1

O(amount × len(coins)) time, O(amount) space.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/coin-change/

STOP. 20-min timer.

3. Prerequisite Concepts

  • 1D DP recurrence with min over multiple transitions.
  • Sentinel value for “impossible” (use float('inf') or amount + 1).
  • Knapsack distinction: unbounded (reuse allowed) vs 0/1 (each item once).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Cheapest way to make change, using each denomination unlimited times.

2. Clarify:

  • Coins distinct? (Yes.) Positive? (Yes.)
  • Amount up to 10⁴; coins up to ~12 distinct on LC.
  • Amount = 0 → return 0.
  • No combination possible → return -1.

3. Constraints: amount ≤ 10⁴, coins.length ≤ 12. O(amount × coins) ≈ 10⁵ ops — trivial.

4. Examples:

  • coins=[1,2,5], amount=11 → 3 (5+5+1).
  • coins=[2], amount=3 → -1.
  • coins=[1], amount=0 → 0.
  • coins=[1,3,4], amount=6 → 2 (3+3, NOT 4+1+1 = 3 coins) — exposes greedy failure.

5. Brute force: Recursive — at each step pick any coin, subtract, recurse. Exponential without memoization.

6. Target: O(amount × len(coins)) time, O(amount) space.

7. Pattern: Unbounded knapsack via bottom-up DP.

8. Develop: see solution.py.

9. Test: amount=0; single coin equal to amount; impossible; greedy-trap input [1,3,4] amount=6.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why greedy fails

Greedy = “always use the largest coin ≤ remaining.” Works for canonical coin systems (US coins {1,5,10,25}). Fails for [1,3,4] amount 6: greedy gives 4+1+1 = 3 coins; optimal = 3+3 = 2 coins.

The general “is this coin system canonical?” question is a known hard problem (Pearson, 2005, polynomial-time test). For arbitrary denominations, DP is required.

6.2 The unbounded recurrence

dp[a] = 1 + min(dp[a - c] for c in coins if c <= a)

Why this works: A solution for amount a ends with some coin c. Strip that coin: you’re left with the optimal solution for a - c. Take the best over all choices of c.

The “unbounded” in unbounded knapsack means: dp[a] looks back at dp[a - c] without modifying the available-coins set — coins are reusable. Contrast with 0/1 knapsack (p61) where dp[a] looks at dp[i-1][a-w] to forbid reuse.

6.3 Two implementation flavors

Bottom-up (iterative, preferred):

dp = [INF] * (amount + 1); dp[0] = 0
for a in 1..amount:
    for c in coins:
        if c <= a:
            dp[a] = min(dp[a], dp[a - c] + 1)

O(amount × coins). O(amount) space.

Top-down (memoized recursion): Equivalent, often slower in Python due to function call overhead. Useful when state space is sparse (it isn’t here).

6.4 BFS interpretation — “shortest path in a state graph”

Reframe: nodes = amounts 0..amount. Edges from a to a + c for each coin c. We seek the shortest path from 0 to amount. BFS works and gives the same complexity (each node enqueued once because the first time we reach it is the shortest).

visited = {0}; queue = deque([(0, 0)])
while queue:
    a, steps = queue.popleft()
    if a == amount: return steps
    for c in coins:
        nxt = a + c
        if nxt <= amount and nxt not in visited:
            visited.add(nxt); queue.append((nxt, steps + 1))
return -1

Same Θ(amount × coins), but the BFS framing is what unlocks Cheapest Flights K Stops (p64) and similar graph-with-state problems.

6.5 The sentinel choice

Use float('inf') or amount + 1 as “impossible” marker. The check dp[amount] > amount works because no real answer can exceed amount (worst case = amount coins of value 1, which requires coin 1 to exist).

6.6 LC 518 Coin Change II — count of combinations, not minimum

Variant: how many distinct combinations sum to amount? The recurrence is different — outer loop on COINS, inner on amount, ensuring each combination is counted once (combinations, not permutations):

dp[0] = 1
for c in coins:
    for a in c..amount: dp[a] += dp[a - c]

The loop order matters: swapping it counts permutations, not combinations. Subtle and a frequent follow-up.

7. Anti-Pattern Analysis

  1. Greedy — fails on non-canonical denominations.
  2. for c in coins; for a in 1..amount loop order for the minimum-coins variant — actually fine here, but be aware the loop order does matter in LC 518 (combinations).
  3. Forgetting dp[0] = 0 — base case missed; returns -1 for amount=0 incorrectly.
  4. Using -1 as the “impossible” sentinel in the DP — breaks min() comparisons; use INF.
  5. Memoization with lru_cache on the recursive top-down in Python without size hint — works but slower.
  6. Returning dp[amount] directly without the -1 check — silently emits a giant sentinel value.

8. Skills & Takeaways

  • Unbounded knapsack template.
  • “Min over previous-state + 1” pattern — analogous to BFS shortest path.
  • Greedy-vs-DP discrimination via tiny counter-example.
  • Connect DP-on-amount to “graph BFS over a state space” — bridge to p64.

9. When to Move On

  • Implement bottom-up in 10 min, O(amount × coins) time, O(amount) space.
  • Articulate the unbounded vs 0/1 distinction in 30 seconds.
  • Solve LC 518 (combinations) and explain the loop-order subtlety.
  • Sketch the BFS reformulation.
  • Give a 5-element counter-example where greedy fails.

10. Company Context

  • Amazon: Bar Raiser favorite. L5+ asked to compare with LC 518.
  • Google: Phone screen L4/L5. Always with a follow-up — either LC 518 or “what if amount were 10⁹?” (answer: DP doesn’t scale; need ILP or denomination-specific tricks).
  • Meta: E5 phone screen; expect “count combinations” follow-up.
  • Microsoft: Common L62 onsite problem.
  • Stripe: Productized as “minimum-units to settle a payment in a multi-currency exchange.”
  • Bloomberg: “Minimum trades to balance a portfolio.”

Scorecard for strong: “Rejected greedy with counter-example, derived recurrence cleanly, articulated unbounded vs 0/1, sketched BFS framing, solved LC 518 follow-up correctly.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Greedy rejectionTries greedy firstTries, then DP after promptSpots failure with counter-example+ canonical-coin-system aside
RecurrenceMemorizedDerived+ correct base + INF sentinel+ alternative BFS framing
LC 518 follow-upDoesn’t knowKnows, can’t solveSolves with right loop order+ explains why loop order matters

12. Level Delta

  • Mid (L4): Bottom-up DP, correct, returns -1 properly.
  • Senior (L5): + BFS framing mentioned + LC 518 solved with correct loop order.
  • Staff (L6): + complexity proof + adversarial input examples + LC 322 reduction to weighted shortest-path in a DAG.
  • Principal (L7+): + canonical-coin-system theorem (when greedy works), + ILP framing for huge-amount variant, + connection to FPTAS schemes for #P-hard subset-sum.

13. Follow-up Q&A

Q1: LC 518 — how many combinations? A1: Same dp array but recurrence sums instead of minimizes. Loop order matters: outer loop on coins, inner on amount, accumulating dp[a] += dp[a - c]. Swapping the loops counts permutations.

Q2: amount = 10⁹, coins.length = 5. DP infeasible. Now what? A2: DP space is amount-dependent; this won’t fit. Options: (a) ILP solver if you only need ≤ K coins; (b) for specific coin structures (e.g., all multiples of g = gcd(coins)), reduce by dividing by g; (c) approximate via the largest coin and remainder. Acknowledge the problem is NP-hard for arbitrary denominations (subset sum reduction).

Q3: What if some coins have negative values? A3: Pathological — chains of negatives create infinite-coin solutions. Problem becomes ill-defined unless you bound the number of coins.

Q4: Streaming: amount fixed, new coin denominations arrive over time. Re-answer after each. A4: When a new coin c arrives, run one extra pass: for a in c..amount: dp[a] = min(dp[a], dp[a-c] + 1). O(amount) per update.

Q5: Track WHICH coins are used. A5: Maintain parent[a] = coin_used_to_reach_a. Backtrack from amount: while a > 0: emit parent[a]; a -= parent[a].

14. Solution Walkthrough

See solution.py:

  • coin_change_dp — bottom-up O(amount × coins).
  • coin_change_bfs — BFS reformulation; same complexity, different mental model.
  • coin_change_brute — recursive without memo, used only for tiny stress (amount ≤ 12).

15. Beyond the Problem

Principal code review: “Coin Change is the most-asked DP for one reason: it sits at the intersection of greedy, DP, and graph BFS. Candidates who derive only the DP miss the point. The interviewer wants to see whether you can reformulate the same problem in three equivalent ways — and reach for the most appropriate one given the input shape. For tiny amount and a few coins, DP. For sparse reachable states, BFS. For canonical coin systems, greedy. Knowing only one of the three is a Mid-level signal; knowing all three and choosing fluidly is L6.”