Coin Change

Problem Description

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Examples

Constraints

• 1 ≤ coins.length ≤ 12
• 1 ≤ coins[i] ≤ 2³¹ - 1
• 0 ≤ amount ≤ 10⁴

Finding the Minimum Steps to Reach Target Values

The greedy approach (always choosing the largest denomination) fails on cases like coins = [1, 3, 4] and amount = 6. Greedy would choose 4 + 1 + 1 (3 coins), whereas the optimal is 3 + 3 (2 coins).

To find the optimal solution, we use dynamic programming. The minimum coins required to make up amount is 1 + min(coin_change(amount - coin)) across all coin denominations.

We compute this bottom-up. Initialize a dp array of size amount + 1 with a placeholder value (like amount + 1, representing infinity). The base case is dp[0] = 0. For each value i from 1 to amount, we iterate over all coins. If i - coin >= 0, we update dp[i] = min(dp[i], 1 + dp[i - coin]). If dp[amount] remains unchanged at the end, it is impossible to form that amount, and we return -1.

Solution 1: Dynamic Programming (Bottom-Up Tabulation)

Iterate from 1 to amount, updating the minimum coins required for each step using values of preceding subproblems.

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // fill with value larger than any possible valid coin count
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // base case

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

        // if dp[amount] is still amount + 1, it means the target is unreachable
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        # fill with value larger than any possible valid coin count
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0  # base case

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

        # if dp[amount] is still amount + 1, the target is unreachable
        return dp[amount] if dp[amount] <= amount else -1

#include <vector>
#include <algorithm>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        // fill with value larger than any possible valid coin count
        std::vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0; // base case

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

        // if dp[amount] is still amount + 1, the target is unreachable
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

Complexity Analysis:

• Time Complexity: O(c * a) where c is the number of coins and a is the target amount. We run nested loops of sizes a and c.
• Space Complexity: O(a) to store the DP table.

Where it breaks: If the amount is extremely large (e.g. 10⁹), allocating the DP table will result in out of memory errors. In those scenarios, you must use BFS recursion with memoization or explore mathematical representations.

Common Mistakes

• Initializing the DP array with Integer.MAX_VALUE. If you do 1 + dp[i - coin] when dp[i - coin] == Integer.MAX_VALUE, it will overflow and become Integer.MIN_VALUE, resulting in incorrect minimum updates. Use amount + 1 as your infinity placeholder instead.
• Not handling the amount == 0 base case correctly. If amount is 0, the loops should not run, and the code must return 0 immediately.
• Attempting to use greedy coin selection. Greedy algorithms will fail on combinations like coins = [9, 6, 5, 1] for amount = 11. Greedy selects 9 + 1 + 1 (3 coins), whereas the optimal is 6 + 5 (2 coins).

Frequently Asked Questions

Why is amount + 1 a safe value for infinity? Because the smallest coin denomination is 1, the maximum possible coins needed to form amount is amount. Any count of amount + 1 is mathematically impossible, making it a safe value to represent unreachable states without risking integer overflow.

How does this change if we have a limited supply of each coin? If coin counts are limited, this becomes the “Bounded Knapsack” problem, requiring a 2D DP state representation where dp[i][j] tracks maximum value using the first i coins.

What does this problem test in interviews? It tests your ability to identify why greedy approaches fail, construct O(n) space DP transition tables, and prevent integer overflows.

← All Problems