Coin Change

medium
Dynamic ProgrammingArrayDynamic Programming

Given an array of coin denominations coins and a target amount amount, return the fewest number of coins needed to make up that amount. If it is not possible to make the amount using the given coins, return -1. You may use each coin denomination an unlimited number of times.

Examples

Example 1

  • Input: coins = [1,5,11], amount = 11
  • Output: 1
  • Explanation: Use one coin of value 11.

Example 2

  • Input: coins = [2], amount = 3
  • Output: -1
  • Explanation: The amount 3 cannot be made with coins of denomination 2.

Example 3

  • Input: coins = [1], amount = 0
  • Output: 0
  • Explanation: Zero coins are needed to make amount 0.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

For each amount, we try subtracting every coin denomination and recursively solve for the remaining amount. The answer for a given amount is 1 + min(coinChange(amount - coin)) over all valid coins. The base cases are: amount 0 needs 0 coins, and a negative amount is impossible. This explores all combinations but has exponential time due to overlapping subproblems.

Algorithm

  1. If `amount == 0`, return `0`.
  2. If `amount < 0`, return `-1` (impossible).
  3. Initialize `minCoins` to infinity.
  4. For each coin, recursively solve `amount - coin` and track the minimum.
  5. Return `minCoins + 1` if any valid solution was found, otherwise `-1`.
TimeO(S^n) where S is the amount and n is the number of coin denominationsSpaceO(S) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int minCoins = INT_MAX;
        for (int coin : coins) {
            int res = coinChange(coins, amount - coin);
            if (res >= 0) {
                minCoins = min(minCoins, res + 1);
            }
        }
        return minCoins == INT_MAX ? -1 : minCoins;
    }
};
Java 21
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, amount - coin);
            if (res >= 0) {
                minCoins = Math.min(minCoins, res + 1);
            }
        }
        return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
    }
}
Python 3.12
from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        if amount < 0:
            return -1
        min_coins = float('inf')
        for coin in coins:
            res = self.coinChange(coins, amount - coin)
            if res >= 0:
                min_coins = min(min_coins, res + 1)
        return min_coins if min_coins != float('inf') else -1
Go 1.26
func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }
    minCoins := math.MaxInt32
    for _, coin := range coins {
        res := coinChange(coins, amount-coin)
        if res >= 0 && res+1 < minCoins {
            minCoins = res + 1
        }
    }
    if minCoins == math.MaxInt32 {
        return -1
    }
    return minCoins
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

We build a DP table where dp[i] represents the minimum number of coins needed to make amount i. For each amount from 1 to the target, we try every coin and take the minimum of dp[i - coin] + 1. We initialize dp[0] = 0 and all other entries to amount + 1 (an impossible upper bound that acts as infinity).

Algorithm

  1. Create array `dp` of size `amount + 1`, filled with `amount + 1`.
  2. Set `dp[0] = 0`.
  3. For each amount `i` from 1 to `amount`, for each coin, if `coin <= i`, update `dp[i] = min(dp[i], dp[i - coin] + 1)`.
  4. Return `dp[amount]` if it is `<= amount`, otherwise `-1`.
TimeO(S * n) where S is the amount and n is the number of coinsSpaceO(S)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};
Java 21
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 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];
    }
}
Python 3.12
from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount] if dp[amount] <= amount else -1
Go 1.26
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i && dp[i-coin]+1 < dp[i] {
                dp[i] = dp[i-coin] + 1
            }
        }
    }
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

Frequently asked questions

What is the optimal time complexity of Coin Change?

The most efficient approach in this guide ("Dynamic Programming (Bottom-Up)") runs in O(S * n) where S is the amount and n is the number of coins time and uses O(S) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Coin Change use?

Coin Change is a medium-level Dynamic Programming problem involving Array, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Coin Change be solved without extra space?

The most space-efficient approach in this guide uses O(S) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(S) for the recursion stack, while the optimized version uses O(S).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
coins=
[1,5,10,25]
amount=
0
Expected Output
0