LeetCode · #322

Coin Change Solution

Given coin denominations and a target amount, return the fewest coins needed to make that amount. Return -1 if impossible.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #322

🏗️

Pattern

DP — unbounded knapsack

You have an infinite supply of coins of given denominations. Return the minimum number of coins to make up amount. If no combination works, return -1.

Example
Input: coins = [1,3,4], amount = 6 Output: 2 // 3 + 3 = 6. Two coins.
Constraints
• 1 ≤ coins.length ≤ 12 • 1 ≤ coins[i] ≤ 2³¹ - 1 • 0 ≤ amount ≤ 10⁴ ← DP array of size 10,001 fits easily
02
Section Two · Approach 1

Greedy / Recursion — incorrect or O(Sⁿ)

Greedy: always use the largest coin first. This fails — e.g., coins=[1,3,4], amount=6: greedy picks 4+1+1=3 coins, but 3+3=2 is optimal. Exhaustive recursion tries all combinations but is exponential.

Why greedy fails

Greedy assumes the largest coin always helps, but sometimes skipping a large coin leads to a better combination. Only DP or BFS over all possible remaining amounts guarantees the minimum.

Why we can do better
Problem: Recursion branches on each coin denomination at each step, giving O(Sⁿ) where S = amount/min_coin. Many subproblems overlap — minCoins(amount=3) is recomputed from multiple paths. Bottom-up DP fills a 1D array from 0 to amount, each cell O(coins) work, total O(amount × coins).
Java — Recursive (TLE)
class Solution { public int coinChange(int[] coins, int amount) { if (amount == 0) return 0; int min = Integer.MAX_VALUE; for (int c : coins) { if (c <= amount) { int res = coinChange(coins, amount - c); if (res >= 0) min = Math.min(min, res + 1); } } return min == Integer.MAX_VALUE ? -1 : min; } }
Python — Recursive (TLE)
class Solution: def coinChange(self, coins: list[int], amount: int) -> int: if amount == 0: return 0 best = float('inf') for c in coins: if c <= amount: res = self.coinChange(coins, amount - c) if res >= 0: best = min(best, res + 1) return best if best < float('inf') else -1
MetricValue
TimeO(Sⁿ) where S = amount/min_coin
SpaceO(amount) call stack
03
Section Three · Approach 2

Bottom-Up DP — O(amount × coins)

Build array dp[0..amount] where dp[a] = minimum coins for amount a. For each amount from 1 to target, try each coin: dp[a] = min(dp[a], dp[a - coin] + 1).

💡 Mental model: Imagine a vending machine change dispenser with an answer board on the wall. The board has slots labeled 0¢ to 100¢. Slot 0 says "0 coins." For each subsequent slot, you check: "If I use a quarter, the remaining is on slot 75 — that says 3 coins, so I'd need 4. If I use a dime, slot 90 says 1 coin, so I'd need 2." You write down the minimum for each slot. When you reach slot 100, you read the answer directly.
Algorithm
  • Create dp[amount+1], fill with amount+1 (impossible sentinel — any valid count ≤ amount).
  • dp[0] = 0.
  • For a from 1 to amount: for each coin, if coin ≤ a: dp[a] = min(dp[a], dp[a-coin] + 1).
  • Return dp[amount] if < amount+1, else -1.
🎯 When to recognize this pattern:
  • "Minimum items from unlimited supply to reach a target" = unbounded knapsack.
  • The signal: each item can be used multiple times, and you minimize (or count) combinations.
  • Also in LC 518 (Coin Change 2 — count combinations), LC 279 (Perfect Squares — treat squares as "coins").
Why amount+1 as sentinel instead of Integer.MAX_VALUE:
  • Using MAX_VALUE risks overflow when computing dp[a-coin] + 1.
  • Since no valid answer can exceed amount (worst case: all 1-cent coins), amount+1 is a safe, overflow-free sentinel.
04
Section Four · Trace

Visual Walkthrough

Trace for coins = [1, 3, 4], amount = 6.

Coin Change — Bottom-Up DP (coins=[1,3,4], amount=6)
dp[a] = min coins to make amount a. Init: dp[0]=0, rest=7 (sentinel). Amount: 0 1 2 3 4 5 6 dp: 0 1 2 1 1 2 2 a=1: coin 1→dp[0]+1=1. dp[1]=1. a=2: coin 1→dp[1]+1=2. dp[2]=2. a=3: coin 1→dp[2]+1=3, coin 3→dp[0]+1=1. dp[3]=1. a=4: coin 1→2, coin 3→2, coin 4→dp[0]+1=1. dp[4]=1. a=5: coin 1→dp[4]+1=2, coin 3→dp[2]+1=3, coin 4→dp[1]+1=2. dp[5]=2. a=6: coin 1→dp[5]+1=3, coin 3→dp[3]+1=2, coin 4→dp[2]+1=3. dp[6]=2. (3+3) return 2 ✓
05
Section Five · Implementation

Code — Java & Python

Java — Bottom-up DP
import java.util.Arrays; class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); // sentinel — no valid answer > amount dp[0] = 0; for (int a = 1; a <= amount; a++) for (int c : coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1); return dp[amount] > amount ? -1 : dp[amount]; } }
Python — Bottom-up DP
class Solution: def coinChange(self, coins: list[int], amount: int) -> int: dp = [amount + 1] * (amount + 1) # sentinel dp[0] = 0 for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount] if dp[amount] <= amount else -1
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpaceTrade-off
GreedyO(amount/min)O(1)Wrong answer — greedy doesn't guarantee minimum
Recursive (brute force)O(Sⁿ)O(amount)Correct but exponential
Bottom-up DP ← optimalO(amount × n)O(amount)n = number of coin types; fills each cell once
BFS alternative: Treat each amount as a graph node and each coin as an edge. BFS from 0 to amount gives the shortest path = minimum coins. Same time/space as DP, but less intuitive for this problem. DP is the standard interview expectation.
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
amount = 0coins=[1], amount=0dp[0]=0. Return 0 — no coins needed.
Impossiblecoins=[2], amount=3dp[3] stays at sentinel. Return -1.
Single coin = 1coins=[1], amount=5Answer is always amount itself (5 pennies).
Exact matchcoins=[5], amount=5dp[5] = dp[0]+1 = 1.
Large amountamount=10000dp array of 10001 ints. O(10000 × 12) = ~120K operations. Fine.
⚠ Common Mistake: Using Integer.MAX_VALUE as the sentinel and then computing dp[a-c] + 1 — this overflows to Integer.MIN_VALUE, which becomes the "minimum" and corrupts the dp array. Always use amount + 1 as the sentinel since no valid answer exceeds amount.

← Back to DP — 1D problems