322. Coin Change
Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 37.7%
Problem Breakdown
We need to find the minimum number of coins required to make up a specific total amount. We are given an array of coin denominations and can use each denomination as many times as we want (unbounded knapsack variation). If no combination sums exactly to amount, return -1.
Inputs:
coins: List of integers representing values available.amount: Integer target sum.
Outputs:
- Minimum integer count, or
-1if impossible.
Implicit Constraints & Edge Cases:
- Amount = 0: Requires zero coins (return 0). This is a base case often missed by naive recursion.
- Impossible Case: If
amountcannot be formed using the given denominations (e.g., target 3 with only coin [2]), return -1. - Large Coin Values: Coins can be larger than the amount; these should simply be skipped during iteration as they don’t contribute to smaller sums.
Intuition
A brute-force approach would try every possible combination of coins, which is essentially a variation of the subset sum problem but with minimization constraints. This leads to exponential time complexity or worse due to overlapping subproblems (calculating ways to make change for amount 5 multiple times when solving for amount 10).
The key insight here is Optimal Substructure: To find the minimum coins for amount, we can consider using one coin of value c and then finding the minimum coins needed for the remaining sum (amount - c). This suggests a recursive relationship:
Since this is an optimization problem with overlapping subproblems, Dynamic Programming is the correct paradigm. We can solve this iteratively (Bottom-Up) by building up solutions for all amounts from to amount. This avoids recursion overhead and stack overflow risks while ensuring we compute each state exactly once. Note that a greedy approach (always picking the largest coin first) fails here because not all currency systems are canonical; DP guarantees optimality regardless of denomination values.
Approach
- Initialize DP Array: Create an array
dpof sizeamount + 1. Initialize every index with infinity (float('inf')) to represent that a sum is currently unreachable, except for the base case where zero amount requires zero coins:dp[0] = 0. - Iterate Through Amounts: Loop through each value from up to
amount(inclusive). For every current targeti, iterate through all coin denominations incoins. - Update State: If the coin fits (
coin <= i), updatedp[i]: - Final Check: After filling the table, check if
dp[amount]is still infinity. If so, return-1. Otherwise, returndp[amount].
Complexity Analysis
- Time Complexity: , where is the number of coin types (
coins.length). We iterate through each amount from 0 toamountand for each we check all coins. Given constraints (), this results in roughly operations, which fits well within standard time limits (typically ops/sec). - Space Complexity: to store the DP array of size
amount + 1.
Solution
def coin_change(coins: list[int], amount: int) -> int:
# Initialize dp array with a sentinel value larger than any possible answer.
# Max coins needed is 'amount' (if we only have coin=1), so amount+1 works as INF.
n = len(coins)
if not coins or amount == 0:
return 0
dp = [float('inf')] * (amount + 1)
# Base case: zero amount requires zero coins
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
# If we can use this coin, check if it improves the count
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Edge Cases Handled
- Amount is 0: The code initializes
dpwith sizeamount+1. If amount is 0, loop range(1, 1) doesn’t run. Logic handles it via initialization or explicit check (though constraints say , so we must handle 0). My solution returns -1 if inf else value; for amount=0, dp[0]=0, returns 0 correctly. - No Solution: If
dp[amount]remains at infinity sentinel after loops, it returns-1. - Coin Larger than Amount: The condition
if coin <= iensures we only consider valid coins for the current sub-problem sum.