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.

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

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
  

Metric	Value
Time	O(Sⁿ) where S = amount/min_coin
Space	O(amount) call stack

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.

Section Four · Trace

Visual Walkthrough

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

Coin Change — Bottom-Up DP (coins=[1,3,4], amount=6)

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
  

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Greedy	O(amount/min)	O(1)	Wrong answer — greedy doesn't guarantee minimum
Recursive (brute force)	O(Sⁿ)	O(amount)	Correct but exponential
Bottom-up DP ← optimal	O(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.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
amount = 0	`coins=[1], amount=0`	dp[0]=0. Return 0 — no coins needed.
Impossible	`coins=[2], amount=3`	dp[3] stays at sentinel. Return -1.
Single coin = 1	`coins=[1], amount=5`	Answer is always amount itself (5 pennies).
Exact match	`coins=[5], amount=5`	dp[5] = dp[0]+1 = 1.
Large amount	`amount=10000`	dp 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

LearningTree

LC 322 · Coin Change — Solution & Explanation | DSA Guide