Coin Change

Medium Problem 119 of 151 Java and Python

Problem

You are given coin denominations coins and a total amount. Return the fewest coins needed to make exactly amount, or -1 if it cannot be made. You have an unlimited number of each coin.

Example 1

Input: coins = [1, 2, 5], amount = 11
Output: 3
Why: 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
0 ≤ amount ≤ 10⁴

Explanation

Greedy (always take the biggest coin) fails: with coins [1, 3, 4] and amount 6, greedy gives 4 + 1 + 1 but 3 + 3 is better.

Instead, the last coin used is some c, so fewest(a) = 1 + min over coins of fewest(a - c). Compute it for every amount from 0 up to amount.

Approach 1 · Naive

Plain recursion

Time O(kᵃ), exponential
Space O(amount) recursion

Try every coin as the last coin and recurse on the remaining amount.

fewest(0) = 0; a negative amount is impossible.
fewest(a) = 1 + min(fewest(a - c)) over all coins, ignoring impossible results.

Java

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int best = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (coin <= amount) {
                int rest = coinChange(coins, amount - coin);
                if (rest != -1) {
                    best = Math.min(best, rest + 1);
                }
            }
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }
}

Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        best = float("inf")
        for coin in coins:
            if coin <= amount:
                rest = self.coinChange(coins, amount - coin)
                if rest != -1:
                    best = min(best, rest + 1)
        return -1 if best == float("inf") else best

Approach 2 · Optimal

Bottom-up DP over amounts

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

Fill dp[a], the fewest coins for amount a, from 0 to amount.

dp[0] = 0; every other entry starts at amount + 1 (an impossible count).
For each a from 1 to amount, for each coin c <= a: dp[a] = min(dp[a], dp[a - c] + 1).
Return dp[amount], or -1 if it is still amount + 1.

Java

import java.util.*;

class Solution {
    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 (coin <= a) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [amount + 1] * amount
        for a in range(1, amount + 1):
            for coin in coins:
                if coin <= a:
                    dp[a] = min(dp[a], dp[a - coin] + 1)
        return -1 if dp[amount] > amount else dp[amount]

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(kᵃ), exponential	O(amount) recursion
Optimal Bottom-up DP over amounts	O(amount · k)	O(amount)

Key takeaways

amount + 1 works as "infinity" because no answer can use more coins than the amount itself.
Counting the number of ways instead is Coin Change II (in the 2-D DP topic).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem