Domain 2MediumCORE

Coin Change

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

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 -1 if 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 amount cannot 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 O(2n)O(2^n) 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: dp[i]=min⁡(dp[i],dp[i−c]+1)dp[i] = \min(dp[i], dp[i-c] + 1)

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 00 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

  1. Initialize DP Array: Create an array dp of size amount + 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.
  2. Iterate Through Amounts: Loop through each value from 11 up to amount (inclusive). For every current target i, iterate through all coin denominations in coins.
  3. Update State: If the coin fits (coin <= i), update dp[i]: dp[i]=min⁡(dp[i],dp[i−coin]+1)dp[i] = \min(dp[i], dp[i - coin] + 1)
  4. Final Check: After filling the table, check if dp[amount] is still infinity. If so, return -1. Otherwise, return dp[amount].

Complexity Analysis

  • Time Complexity: O(amount×n)O(amount \times n), where nn is the number of coin types (coins.length). We iterate through each amount from 0 to amount and for each we check all coins. Given constraints (104×1210^4 \times 12), this results in roughly 1.2×1051.2 \times 10^5 operations, which fits well within standard time limits (typically ≈108\approx 10^8 ops/sec).
  • Space Complexity: O(amount)O(amount) 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 dp with size amount+1. If amount is 0, loop range(1, 1) doesn’t run. Logic handles it via initialization or explicit check (though constraints say 0≤amount0 \le amount, 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 <= i ensures we only consider valid coins for the current sub-problem sum.