Coin Change

NeetCode: Coin Change · LeetCode: 322. Coin Change · Difficulty: Medium

Given coin denominations coins (unlimited supply of each) and a target amount, return the fewest coins needed to make that amount, or -1 if it cannot be made.

Example

Text

Input:  coins = [1, 2, 5], amount = 11    Output: 3    (5 + 5 + 1)
Input:  coins = [2], amount = 3           Output: -1
Input:  coins = [1], amount = 0           Output: 0

Greedy (always take the biggest coin) fails in general: for coins [1, 3, 4] and amount 6 it gives 4+1+1 (3 coins), but the best is 3+3 (2 coins). Instead, the answer for amount a is 1 + min(answer(a - c)) over every coin c <= a.

Brute force: recursion over the remaining amount

The helper returns the fewest coins for the remaining amount, or -1 when that amount cannot be made, the same convention as the problem's answer.

Java

class Solution {
    // Fewest coins for rem, or -1 if rem cannot be made.
    private int solve(int[] coins, int rem) {
        if (rem == 0) {
            return 0;
        }
        int best = -1;
        for (int c : coins) {
            if (c <= rem) {
                int sub = solve(coins, rem - c);
                if (sub >= 0 && (best == -1 || sub + 1 < best)) {
                    best = sub + 1;
                }
            }
        }
        return best;
    }

    public int coinChange(int[] coins, int amount) {
        return solve(coins, amount);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(solution.coinChange(new int[]{2}, 3));
        System.out.println(solution.coinChange(new int[]{1}, 0));
        System.out.println(solution.coinChange(new int[]{1, 3, 4}, 6));
    }
}

Output

Each level branches into up to k coins, and the same remaining amounts are reached through many orderings of coins. Time: exponential, up to O(k^amount). Space: O(amount) stack.

Better: memoization (top-down)

There are only amount + 1 distinct remaining amounts. Cache each result in an int array: -1 means impossible and -2 means not computed yet. Arrays.fill sets every slot to -2, because a new int array starts at 0, which is a real answer.

Java

import java.util.Arrays;

class Solution {
    private int solve(int[] coins, int rem, int[] memo) {
        if (rem == 0) {
            return 0;
        }
        if (memo[rem] != -2) {
            return memo[rem];
        }
        int best = -1;
        for (int c : coins) {
            if (c <= rem) {
                int sub = solve(coins, rem - c, memo);
                if (sub >= 0 && (best == -1 || sub + 1 < best)) {
                    best = sub + 1;
                }
            }
        }
        memo[rem] = best;
        return best;
    }

    public int coinChange(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -2);
        return solve(coins, amount, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(solution.coinChange(new int[]{2}, 3));
        System.out.println(solution.coinChange(new int[]{1}, 0));
        System.out.println(solution.coinChange(new int[]{1, 3, 4}, 6));
    }
}

Output

Time: O(amount · k). Space: O(amount) for the table and the stack.

Optimal: bottom-up table

Build dp[a] for a = 0, 1, ..., amount in order: dp[0] = 0, and dp[a] = 1 + min(dp[a - c]) over coins c <= a. amount + 1 serves as infinity, since no valid answer can exceed amount coins (every coin is worth at least 1). Using Integer.MAX_VALUE instead would overflow to a negative number in dp[a - c] + 1, so the smaller sentinel is the safe choice. Bottom-up also avoids deep recursion.

Java

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int inf = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, inf);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) {
                    dp[a] = Math.min(dp[a], dp[a - c] + 1);
                }
            }
        }
        return dp[amount] >= inf ? -1 : dp[amount];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(solution.coinChange(new int[]{2}, 3));
        System.out.println(solution.coinChange(new int[]{1}, 0));
        System.out.println(solution.coinChange(new int[]{1, 3, 4}, 6));
    }
}

Output

Time: O(amount · k). Space: O(amount).