Coin Change Problem

Generated on 2025-07-10 02:02:22 Algorithm Cheatsheet for Technical Interviews

---

Coin Change Problem Cheatsheet

1. Quick Overview

What is it? Given a set of coin denominations coins and a target amount amount, find the minimum number of coins needed to make up that amount. If the amount cannot be made up by any combination of the coins, return -1.

When to use it? When you need to find the minimum number of items (coins, steps, etc.) required to reach a target value, and you have a set of possible choices (coin denominations, step sizes, etc.). This problem is a classic example of dynamic programming.

2. Time & Space Complexity

Approach	Time Complexity	Space Complexity
Recursive (Naive)	O(coinsamount)	O(amount) (call stack)
Dynamic Programming (Top-Down - Memoization)	O(amount *	coins
Dynamic Programming (Bottom-Up - Tabulation)	O(amount *	coins

3. Implementation

Here are examples in Python, Java, and C++ using the bottom-up dynamic programming (tabulation) approach:

Python:

def coin_change(coins, amount):
    """
    Finds the minimum number of coins to make up the amount.

    Args:
        coins: A list of coin denominations.
        amount: The target amount.

    Returns:
        The minimum number of coins, or -1 if it's not possible.
    """
    dp = [float('inf')] * (amount + 1)  # Initialize DP table
    dp[0] = 0  # Base case: 0 amount needs 0 coins

    for a in range(1, amount + 1): # Iterate through amounts
        for coin in coins:  # Iterate through coin denominations
            if a - coin >= 0:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage:
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # Output: 3

Java:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // Initialize with a value greater than amount (impossible number of coins)
        dp[0] = 0; // Base case

        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (a - coin >= 0) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

// Example usage:
// Solution sol = new Solution();
// int[] coins = {1, 2, 5};
// int amount = 11;
// System.out.println(sol.coinChange(coins, amount)); // Output: 3

C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // For INT_MAX

using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1); // Initialize with a value greater than amount.  Also using INT_MAX can lead to overflow when adding 1
    dp[0] = 0; // Base case

    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (a - coin >= 0) {
                dp[a] = min(dp[a], dp[a - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

// Example usage:
// int main() {
//     vector<int> coins = {1, 2, 5};
//     int amount = 11;
//     cout << coinChange(coins, coins, amount) << endl; // Output: 3
//     return 0;
// }

4. Common Patterns

• Minimum/Maximum Problems: Look for problems asking for the minimum/maximum number of steps, coins, operations, etc.
• Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems.
• Overlapping Subproblems: The problem involves solving the same subproblems multiple times. Dynamic programming avoids recomputation.
• Unbounded Knapsack: The coin change problem is a variation of the unbounded knapsack problem, where you can use each coin denomination as many times as you want.

5. Pro Tips

• Initialization: Carefully initialize the DP table. The base case (amount 0) usually requires 0 coins. Initialize the rest with a large value (e.g., float('inf') in Python, amount + 1 in Java/C++).
• Order of Iteration: The order in which you iterate through the amounts and coin denominations matters. In the bottom-up approach, iterate through amounts first, then through coins.
• Edge Cases: Handle edge cases like amount = 0 or when the amount cannot be made up by the given coins.
• Overflow: Be cautious of potential integer overflow when calculating the minimum number of coins, especially when using INT_MAX in C++. Using amount + 1 is generally safer.

6. Practice Problems

1. LeetCode 322. Coin Change: (Standard Coin Change Problem)
2. LeetCode 518. Coin Change 2: (Number of Combinations instead of Minimum Coins)
3. LeetCode 279. Perfect Squares: (Finding the minimum number of perfect square numbers that sum to n - similar application of DP)

7. Templates

Here are reusable code templates in Python, Java, and C++ for the Coin Change problem using bottom-up dynamic programming:

Python:

def coin_change_template(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if a - coin >= 0:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Java:

class CoinChangeTemplate {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (a - coin >= 0) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int coinChangeTemplate(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (a - coin >= 0) {
                dp[a] = min(dp[a], dp[a - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}