Coin Change

LeetCode 322: Coin Change Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a 1D Dynamic Programming array where each index i stores the minimum coins needed to reach amount i, calculated by iterating through all coin denominations.

In the LeetCode 322 problem, commonly known as Coin Change, you are provided with an array of integers representing coin denominations and a target integer representing a total amount of money. The goal is to determine the fewest number of coins required to sum exactly to that total. If the total cannot be formed by any combination of the given coins, the function must return -1. You are assumed to have an infinite supply of each coin denomination.

This is a classic optimization problem frequently seen in technical interviews at top-tier tech companies.

Brute Force Approach for Coin Change

The naive approach to solving the Coin Change problem involves exploring every possible combination of coins that sum up to the target amount. This is typically implemented using recursion.

For a target amount $A$, the algorithm tries to subtract every coin $c$ in the coins array and recursively solves for the remaining amount $A - c$. The base case is when the amount is 0 (requiring 0 coins). The result for amount $A$ is $1 + \min(\text{recursive results})$.

Pseudo-code:

function minCoins(amount):
    if amount == 0: return 0
    if amount < 0: return infinity
    
    min_needed = infinity
    for coin in coins:
        res = minCoins(amount - coin)
        if res != infinity:
            min_needed = min(min_needed, res + 1)
            
    return min_needed

Time Complexity: $O(S^n)$, where $S$ is the amount and $n$ is the number of coin denominations. In the worst case (e.g., coins = [1]), the recursion tree has a depth of $S$, and at each step, it branches $n$ times. Why it fails: This approach fails due to Time Limit Exceeded (TLE) on larger inputs. The recursion tree contains massive redundancy; the subproblem for a specific remaining amount (e.g., "how many coins for amount 5") is recalculated exponentially many times across different branches of the tree.

Algorithm Strategy: DP - 1D Array

1. Initialization: Create a dp array of size amount + 1. Initialize dp[0] = 0 and all other dp[i] to amount + 1. We use amount + 1 as a sentinel value effectively representing infinity because the maximum possible coins needed is amount (using only coins of value 1).
2. Iteration: Loop through every integer i from 1 to amount.
3. Transition: Inside the loop for i, iterate through each coin denomination c:
   • If c <= i, it is possible to use this coin.
   • Update dp[i] using the recurrence relation: dp[i] = min(dp[i], dp[i - c] + 1).
4. Result: After filling the table, check dp[amount].
   • If dp[amount] > amount, it means the target is unreachable. Return -1.
   • Otherwise, return dp[amount].

This strategy is an implementation of the Unbounded Knapsack problem where item weights are coin values, item values are all 1 (cost), and we minimize the total cost.

Execution Flow

Consider coins = [1, 2, 5] and amount = 6.

1. Setup: dp array of size 7: [0, 7, 7, 7, 7, 7, 7] (Using 7 as infinity).

2. Processing i = 1:

   • Coin 1: dp[1] = min(7, dp[0] + 1) -> min(7, 1) -> 1.
   • Coins 2, 5: Ignored (too large).
   • dp: [0, 1, 7, 7, 7, 7, 7]

3. Processing i = 2:

   • Coin 1: dp[2] = min(7, dp[1] + 1) -> min(7, 2) -> 2.
   • Coin 2: dp[2] = min(2, dp[0] + 1) -> min(2, 1) -> 1.
   • dp: [0, 1, 1, 7, 7, 7, 7]

4. Processing i = 3:

   • Coin 1: dp[3] = min(7, dp[2] + 1) -> 2.
   • Coin 2: dp[3] = min(2, dp[1] + 1) -> 2.
   • dp: [0, 1, 1, 2, 7, 7, 7]

5. Processing i = 4:

   • Calculations yield dp[4] = 2 (using two 2s).

6. Processing i = 5:

   • Coin 1: dp[5] = min(7, dp[4] + 1) -> 3.
   • Coin 2: dp[5] = min(3, dp[3] + 1) -> 3.
   • Coin 5: dp[5] = min(3, dp[0] + 1) -> 1.
   • dp: [0, 1, 1, 2, 2, 1, 7]

7. Processing i = 6:

   • Coin 1: dp[6] = min(7, dp[5] + 1) -> 2.
   • Coin 2: dp[6] = min(2, dp[4] + 1) -> 3 (Ignored).
   • Coin 5: dp[6] = min(2, dp[1] + 1) -> 2.
   • dp: [0, 1, 1, 2, 2, 1, 2]

8. Final Result: dp[6] is 2.

Proof of Correctness

The correctness relies on mathematical induction.

• Base Case: dp[0] = 0 is correct; 0 coins make sum 0.
• Inductive Step: Assume dp[k] contains the optimal minimum coin count for all k < i. To find the optimal solution for i, the last coin added must be one of the available denominations, say c. If the last coin was c, the previous state was i - c. Since i - c < i, dp[i - c] is already optimal by hypothesis. By checking all valid c and taking the minimum of dp[i - c] + 1, we guarantee that dp[i] is optimal.

Pattern Reuse Notes

The DP - 1D Array pattern used in LeetCode 322 is highly versatile.

• LeetCode 377: Combination Sum IV: Uses the exact same loop structure. The only difference is that instead of min(), you sum the values: dp[i] += dp[i - coin].
• LeetCode 518: Coin Change II: Calculates the number of ways to make the amount (combinations). The logic is similar, but the order of the loops is swapped (outer loop coins, inner loop amount) to avoid counting permutations.

Reference Implementation

C++ Solution for LeetCode 322

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int coinChange(std::vector<int>& coins, int amount) {
7        // Initialize dp array with value > amount (representing infinity)
8        // Size is amount + 1 to handle indices 0 to amount
9        std::vector<int> dp(amount + 1, amount + 1);
10        
11        // Base case: 0 coins needed for amount 0
12        dp[0] = 0;
13        
14        // Build the table bottom-up
15        for (int i = 1; i <= amount; ++i) {
16            for (int coin : coins) {
17                if (i - coin >= 0) {
18                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
19                }
20            }
21        }
22        
23        // If dp[amount] is still the initial value, it's unreachable
24        return (dp[amount] > amount) ? -1 : dp[amount];
25    }
26};

Java Solution for LeetCode 322

1import java.util.Arrays;
2
3class Solution {
4    public int coinChange(int[] coins, int amount) {
5        // Initialize dp array. Size is amount + 1.
6        int[] dp = new int[amount + 1];
7        
8        // Fill with amount + 1 to represent infinity. 
9        // We avoid Integer.MAX_VALUE to prevent overflow when adding 1.
10        Arrays.fill(dp, amount + 1);
11        
12        // Base case
13        dp[0] = 0;
14        
15        // Iterate through all amounts from 1 to target
16        for (int i = 1; i <= amount; i++) {
17            for (int coin : coins) {
18                if (i - coin >= 0) {
19                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
20                }
21            }
22        }
23        
24        // Check if the amount was reachable
25        return dp[amount] > amount ? -1 : dp[amount];
26    }
27}

Python Solution for LeetCode 322

1class Solution:
2    def coinChange(self, coins: List[int], amount: int) -> int:
3        # Initialize dp array with a value larger than any possible solution
4        # float('inf') is also a valid choice
5        dp = [amount + 1] * (amount + 1)
6        
7        # Base case
8        dp[0] = 0
9        
10        # Iterate through all amounts
11        for i in range(1, amount + 1):
12            for coin in coins:
13                if i - coin >= 0:
14                    dp[i] = min(dp[i], dp[i - coin] + 1)
15                    
16        # If dp[amount] remains larger than amount, return -1
17        return dp[amount] if dp[amount] <= amount else -1