Coin Change

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.

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3 Output: -1

Example 3:

Input: coins = [1], amount = 0 Output: 0

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Approach: Dynamic Programming (Bottom-Up)

Algorithm

1. Let dp[i] be the fewest number of coins needed to make amount i
2. Initialize dp[0] = 0 and every other entry to a large value (e.g., amount + 1)
3. For each amount i from 1 to amount, try every coin: if i - coin >= 0, then dp[i] = min(dp[i], dp[i - coin] + 1)
4. If dp[amount] is still the large sentinel value, return -1; otherwise return dp[amount]

Time & Space Complexity

• Time Complexity: O(amount × coins.length) - nested loop over amounts and coins
• Space Complexity: O(amount) - the dp array

Java Implementation

import java.util.Arrays;

public class CoinChange {

    /**
     * Return the fewest number of coins needed to make up the amount.
     * @param coins Coin denominations (unlimited supply)
     * @param amount Target amount
     * @return Minimum number of coins, or -1 if impossible
     */
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

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

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

    // Test method
    public static void main(String[] args) {
        int[] coins1 = {1, 2, 5};
        int amount1 = 11;
        System.out.println("Input: coins = [1, 2, 5], amount = 11");
        System.out.println("Output: " + coinChange(coins1, amount1)); // Expected: 3

        int[] coins2 = {2};
        int amount2 = 3;
        System.out.println("Input: coins = [2], amount = 3");
        System.out.println("Output: " + coinChange(coins2, amount2)); // Expected: -1

        int[] coins3 = {1};
        int amount3 = 0;
        System.out.println("Input: coins = [1], amount = 0");
        System.out.println("Output: " + coinChange(coins3, amount3)); // Expected: 0
    }
}

Example Walkthrough

For coins = [1, 2, 5] and amount = 11:

1. dp[0] = 0
2. dp[1] = min(dp[1], dp[0] + 1) = 1
3. dp[2] = min(dp[2], dp[1] + 1, dp[0] + 1) = 1 (using coin 2)
4. … and so on
5. dp[10] = min(dp[10], dp[5] + 1) = 2 (two 5s)
6. dp[11] = min(dp[11], dp[10] + 1, dp[6] + 1) = 3 (5 + 5 + 1)

Answer: 3.

Key Points

1. Unbounded Knapsack: Each coin has an unlimited supply
2. Sentinel Value: Use amount + 1 to detect impossible amounts, avoiding overflow
3. Subproblem Structure: dp[i] depends only on smaller amounts dp[i - coin]
4. Unreachable Amounts: If dp[amount] remains the sentinel, return -1
5. Zero Amount: dp[0] = 0 correctly returns 0 coins for amount 0