Coin Change (LeetCode 322)
You're given an array coins of coin denominations, each reusable as many times as you like, and a target amount of money.
Work out the smallest number of coins whose values add up to exactly amount, or return -1 if no combination of the given coins reaches that amount exactly.
Worked Examples
coins = [1,2,5], amount = 113coins = [2], amount = 3-12 can only make even amounts, never 3.coins = [1], amount = 000 needs no coins.⚖️Formal Constraints & Bounds
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Core Insight
dp[i] is the minimum number of coins that sum to i, built only from dp[j] values for j < i that are already finalized, so dp[i] = min(dp[i - coin] + 1) over every coin that fits — that is why the inner loop tries every denomination and takes a min instead of guessing one.
Greedy ("always take the largest coin that fits") is not safe: with denominations [1, 2, 5] greedy happens to work, but with coins = [1, 3, 4], amount = 6, greedy grabs 4 first (largest that fits), leaving 2, which forces two more 1s for a total of 4 + 1 + 1 = 3 coins, when 3 + 3 = 2 coins is optimal. A locally-best coin can leave a remainder that is locally worse to finish than a slightly smaller coin would have, which is why the amounts smaller than i must be solved to true optimality first rather than guessed.
The trap: dp[i - coin] is allowed to itself have used coin again, since nothing in the recurrence marks a denomination as consumed — treat the supply as unbounded, not one-use-per-coin.
Real-World Scenario & Production Applications
When dispensing change in an ATM, vending machine, or cash register with arbitrary coin denominations, you must find the minimum count of coins needed to make up a given amount.
Subproblems & Recurrence Decomposition3 Phases
Zero coins are required to make amount 0 (dp[0] = 0). All other amounts are initialized to infinity (float('inf')) to represent unreachable states before computation.
# Base State Anchor
dp = [0] + [float("inf")] * amountStep-by-Step Execution Trace Table
dp[i] | Candidates Considered (dp[i − coin] + 1) | Winning Transition | dp[i] Value |
|---|---|---|---|
dp[0] | — (Base case: making 0 costs 0 coins) | Base identity | 0 |
dp[1] | coin 1 dp[0] + 1 = 1 | coin 1 | 1 |
dp[2] | coin 1 dp[1] + 1 = 2; coin 2 dp[0] + 1 = 1 | coin 2 | 1 |
dp[3] | coin 1 dp[2] + 1 = 2; coin 2 dp[1] + 1 = 2 | tie (1 or 2) | 2 |
dp[4] | coin 1 dp[3] + 1 = 3; coin 2 dp[2] + 1 = 2 | coin 2 | 2 |
dp[5] | coin 1 dp[4] + 1 = 3; coin 2 dp[3] + 1 = 3; coin 5 dp[0] + 1 = 1 | coin 5 | 1 |
dp[6] | coin 1 dp[5] + 1 = 2; coin 2 dp[4] + 1 = 3; coin 5 dp[1] + 1 = 2 | tie (1 or 5) | 2 |
dp[7] | coin 1 dp[6] + 1 = 3; coin 2 dp[5] + 1 = 2; coin 5 dp[2] + 1 = 2 | coin 2 or 5 | 2 |
dp[8] | coin 1 dp[7] + 1 = 3; coin 2 dp[6] + 1 = 3; coin 5 dp[3] + 1 = 3 | tie | 3 |
dp[9] | coin 1 dp[8] + 1 = 4; coin 2 dp[7] + 1 = 3; coin 5 dp[4] + 1 = 3 | coin 2 or 5 | 3 |
dp[10] | coin 1 dp[9] + 1 = 4; coin 2 dp[8] + 1 = 4; coin 5 dp[5] + 1 = 2 | coin 5 | 2 |
dp[11] | coin 1 dp[10] + 1 = 3; coin 2 dp[9] + 1 = 4; coin 5 dp[6] + 1 = 3 | coin 1 or 5 | 3 |
| 1 | dp = [inf] * (amount + 1) |
| 2 | dp[0] = 0 |
| 3 | for coin in coins: |
| 4 | for w in range(coin, amount + 1): |
| 5 | dp[w] = min(dp[w], dp[w - coin] + 1) |
| 6 | return dp[amount] if dp[amount] != inf else -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Coin Change is an Unbounded Knapsack problem: each coin denomination can be reused an unlimited number of times. Greedy choices fail because taking the largest coin can leave an amount that requires suboptimal change. Giving every amount its own answer, , and processing one coin at a time guarantees optimal substructure in time and space.
The Analogy: One Coin at a Time, Counting Upward
Imagine you add the coin denominations to your pocket one at a time. Before any coin, only $0 is reachable, with zero coins. When a new coin arrives, walk the amounts from that coin's value upward: for each amount $w, ask "is it better to use this coin once more on top of the best way to make $w minus the coin, or to keep what I had?" Because you walk upward, the best way to make the smaller amount may already include this very coin, so the coin can repeat as often as needed.
🔑 The Key Idea in the Code
The loop direction is the whole difference from 0/1 Knapsack: for w in range(coin, amount + 1) goes upward, so dp[w - coin] has already been updated by the current coin. Walking downward would read it before the update and use each coin at most once.
Initializing DP table with 0 instead of infinity: Initializing with 0 causes
min(dp[i], dp[i - coin] + 1)to always select 0. Initialize all entries tofloat('inf')and explicitly setdp[0] = 0.Coin values larger than target amount: When
coin > i, array accessi - coingoes negative, reading from the end of the array in Python. Guard withif i >= coin:.Unreachable amounts returning infinity: If
dp[amount] == float('inf'), return-1per problem specification.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Optimization asking for minimum/maximum elements to reach a sum + unlimited reuse + greedy choices fail.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Optimal Recurrence: dp[a] = min(dp[a - c] + 1) for all coins c <= a. Invariant: when evaluating dp[a], all entries dp[0..a-1] are final.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Target amount is 0: must return 0 immediately without taking any coins.
Negative index: check
a - coin >= 0before indexingdp[a - coin].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use dynamic programming with a 1D array dp of size amount + 1. Base case dp[0] = 0 and all other cells initialized to infinity. For each amount from 1 to target, I iterate through all coins and take dp[a] = min(dp[a], dp[a - c] + 1). Time complexity is O(amount * len(coins)) and space is O(amount)."
Complexity & Mathematical Proof
O(Amount · N)
Look at the nested loops in our tabulation code: The outer loop for a in range(1, amount + 1): iterates through all A subproblem remainder amounts. The inner loop for c in coins: iterates through all N coin denominations. Inside the inner loop, we perform a single constant-time table lookup and comparison dp[a] = min(dp[a], 1 + dp[a - c]) taking O(1) operations. Total operations is exactly the subproblem count multiplied by transitions: (A + 1) · N = O(A · N) time.
O(Amount) Auxiliary
Look at our memory allocations: We allocate a single 1D array dp = [float('inf')] * (amount + 1) of size A + 1 to memoize the minimum coins needed for each amount from 0 up to A. The call stack is iterative O(1) with zero recursion frames. Auxiliary space is strictly O(A).
T(A, N) = A · N = O(A · N)
Derivation Progression
A + 1 states
Outer for loop computes optimal coin counts for amounts 0, 1, 2, ..., A.
N coin branches per state
Inner for loop tests each of the N coin denominations in O(1) table lookup per coin.
O(A · N)
(A + 1) subproblem states multiplied by N coin transitions yields strictly O(A · N) time.
Variable Definitions
Target amount value (0 to Amount table entries)
Number of coin denominations
Memory Architecture & Bounds
O(1) Iterative loops with zero recursion stack frames
O(A) 1D array dp of size amount + 1
O(1) Returns integer minimum coin count
Boundary Best / Worst Cases
for amount = 0.
.
general case.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "fewest number of coins to make up that amount", "unlimited number of each coin". 1D Unbounded Knapsack: you want to minimize cost with infinite item reuse. The optimal number of coins to make amount depends solely on the minimum coins needed for amounts .
. Time budget: operations (ms). Memory budget: array.
Unreachable amounts: initialize with float('inf') or amount + 1. Return -1 if .
Coin Change (LeetCode 322)
You're given an array coins of coin denominations, each reusable as many times as you like, and a target amount of money.
Work out the smallest number of coins whose values add up to exactly amount, or return -1 if no combination of the given coins reaches that amount exactly.
Worked Examples
coins = [1,2,5], amount = 113coins = [2], amount = 3-12 can only make even amounts, never 3.coins = [1], amount = 000 needs no coins.⚖️Formal Constraints & Bounds
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Core Insight
dp[i] is the minimum number of coins that sum to i, built only from dp[j] values for j < i that are already finalized, so dp[i] = min(dp[i - coin] + 1) over every coin that fits — that is why the inner loop tries every denomination and takes a min instead of guessing one.
Greedy ("always take the largest coin that fits") is not safe: with denominations [1, 2, 5] greedy happens to work, but with coins = [1, 3, 4], amount = 6, greedy grabs 4 first (largest that fits), leaving 2, which forces two more 1s for a total of 4 + 1 + 1 = 3 coins, when 3 + 3 = 2 coins is optimal. A locally-best coin can leave a remainder that is locally worse to finish than a slightly smaller coin would have, which is why the amounts smaller than i must be solved to true optimality first rather than guessed.
The trap: dp[i - coin] is allowed to itself have used coin again, since nothing in the recurrence marks a denomination as consumed — treat the supply as unbounded, not one-use-per-coin.
Real-World Scenario & Production Applications
When dispensing change in an ATM, vending machine, or cash register with arbitrary coin denominations, you must find the minimum count of coins needed to make up a given amount.
Subproblems & Recurrence Decomposition3 Phases
Zero coins are required to make amount 0 (dp[0] = 0). All other amounts are initialized to infinity (float('inf')) to represent unreachable states before computation.
# Base State Anchor
dp = [0] + [float("inf")] * amountStep-by-Step Execution Trace Table
dp[i] | Candidates Considered (dp[i − coin] + 1) | Winning Transition | dp[i] Value |
|---|---|---|---|
dp[0] | — (Base case: making 0 costs 0 coins) | Base identity | 0 |
dp[1] | coin 1 dp[0] + 1 = 1 | coin 1 | 1 |
dp[2] | coin 1 dp[1] + 1 = 2; coin 2 dp[0] + 1 = 1 | coin 2 | 1 |
dp[3] | coin 1 dp[2] + 1 = 2; coin 2 dp[1] + 1 = 2 | tie (1 or 2) | 2 |
dp[4] | coin 1 dp[3] + 1 = 3; coin 2 dp[2] + 1 = 2 | coin 2 | 2 |
dp[5] | coin 1 dp[4] + 1 = 3; coin 2 dp[3] + 1 = 3; coin 5 dp[0] + 1 = 1 | coin 5 | 1 |
dp[6] | coin 1 dp[5] + 1 = 2; coin 2 dp[4] + 1 = 3; coin 5 dp[1] + 1 = 2 | tie (1 or 5) | 2 |
dp[7] | coin 1 dp[6] + 1 = 3; coin 2 dp[5] + 1 = 2; coin 5 dp[2] + 1 = 2 | coin 2 or 5 | 2 |
dp[8] | coin 1 dp[7] + 1 = 3; coin 2 dp[6] + 1 = 3; coin 5 dp[3] + 1 = 3 | tie | 3 |
dp[9] | coin 1 dp[8] + 1 = 4; coin 2 dp[7] + 1 = 3; coin 5 dp[4] + 1 = 3 | coin 2 or 5 | 3 |
dp[10] | coin 1 dp[9] + 1 = 4; coin 2 dp[8] + 1 = 4; coin 5 dp[5] + 1 = 2 | coin 5 | 2 |
dp[11] | coin 1 dp[10] + 1 = 3; coin 2 dp[9] + 1 = 4; coin 5 dp[6] + 1 = 3 | coin 1 or 5 | 3 |
| 1 | dp = [inf] * (amount + 1) |
| 2 | dp[0] = 0 |
| 3 | for coin in coins: |
| 4 | for w in range(coin, amount + 1): |
| 5 | dp[w] = min(dp[w], dp[w - coin] + 1) |
| 6 | return dp[amount] if dp[amount] != inf else -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Coin Change is an Unbounded Knapsack problem: each coin denomination can be reused an unlimited number of times. Greedy choices fail because taking the largest coin can leave an amount that requires suboptimal change. Giving every amount its own answer, , and processing one coin at a time guarantees optimal substructure in time and space.
The Analogy: One Coin at a Time, Counting Upward
Imagine you add the coin denominations to your pocket one at a time. Before any coin, only $0 is reachable, with zero coins. When a new coin arrives, walk the amounts from that coin's value upward: for each amount $w, ask "is it better to use this coin once more on top of the best way to make $w minus the coin, or to keep what I had?" Because you walk upward, the best way to make the smaller amount may already include this very coin, so the coin can repeat as often as needed.
🔑 The Key Idea in the Code
The loop direction is the whole difference from 0/1 Knapsack: for w in range(coin, amount + 1) goes upward, so dp[w - coin] has already been updated by the current coin. Walking downward would read it before the update and use each coin at most once.
Initializing DP table with 0 instead of infinity: Initializing with 0 causes
min(dp[i], dp[i - coin] + 1)to always select 0. Initialize all entries tofloat('inf')and explicitly setdp[0] = 0.Coin values larger than target amount: When
coin > i, array accessi - coingoes negative, reading from the end of the array in Python. Guard withif i >= coin:.Unreachable amounts returning infinity: If
dp[amount] == float('inf'), return-1per problem specification.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Optimization asking for minimum/maximum elements to reach a sum + unlimited reuse + greedy choices fail.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Optimal Recurrence: dp[a] = min(dp[a - c] + 1) for all coins c <= a. Invariant: when evaluating dp[a], all entries dp[0..a-1] are final.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Target amount is 0: must return 0 immediately without taking any coins.
Negative index: check
a - coin >= 0before indexingdp[a - coin].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use dynamic programming with a 1D array dp of size amount + 1. Base case dp[0] = 0 and all other cells initialized to infinity. For each amount from 1 to target, I iterate through all coins and take dp[a] = min(dp[a], dp[a - c] + 1). Time complexity is O(amount * len(coins)) and space is O(amount)."
Complexity & Mathematical Proof
O(Amount · N)
Look at the nested loops in our tabulation code: The outer loop for a in range(1, amount + 1): iterates through all A subproblem remainder amounts. The inner loop for c in coins: iterates through all N coin denominations. Inside the inner loop, we perform a single constant-time table lookup and comparison dp[a] = min(dp[a], 1 + dp[a - c]) taking O(1) operations. Total operations is exactly the subproblem count multiplied by transitions: (A + 1) · N = O(A · N) time.
O(Amount) Auxiliary
Look at our memory allocations: We allocate a single 1D array dp = [float('inf')] * (amount + 1) of size A + 1 to memoize the minimum coins needed for each amount from 0 up to A. The call stack is iterative O(1) with zero recursion frames. Auxiliary space is strictly O(A).
T(A, N) = A · N = O(A · N)
Derivation Progression
A + 1 states
Outer for loop computes optimal coin counts for amounts 0, 1, 2, ..., A.
N coin branches per state
Inner for loop tests each of the N coin denominations in O(1) table lookup per coin.
O(A · N)
(A + 1) subproblem states multiplied by N coin transitions yields strictly O(A · N) time.
Variable Definitions
Target amount value (0 to Amount table entries)
Number of coin denominations
Memory Architecture & Bounds
O(1) Iterative loops with zero recursion stack frames
O(A) 1D array dp of size amount + 1
O(1) Returns integer minimum coin count
Boundary Best / Worst Cases
for amount = 0.
.
general case.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "fewest number of coins to make up that amount", "unlimited number of each coin". 1D Unbounded Knapsack: you want to minimize cost with infinite item reuse. The optimal number of coins to make amount depends solely on the minimum coins needed for amounts .
. Time budget: operations (ms). Memory budget: array.
Unreachable amounts: initialize with float('inf') or amount + 1. Return -1 if .