72. Coin Change · DSA Practice

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

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

Explanation: Only even amounts can be made with 2s.

Hint 1

Greedy (largest coin first) fails for coins like [1, 3, 4] and amount 6.

Hint 2

dp[a] = 1 + min(dp[a − c]) over every coin c ≤ a.

Dynamic ProgrammingBFS

Approach 1: Recursion

Try every coin at every step.

⏱ Time Exponential💾 Space O(amount)

Approach 2: Bottom-up DP

Fill dp[0..amount].

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

Approach 3: BFS ✅

Shortest path where each edge adds one coin.

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

Reference solution for BFS (time O(amount · k), space O(amount)). Each solution passes every test in all four languages.

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

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];           // dp[a] = fewest coins for amount a
        Arrays.fill(dp, amount + 1);
        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] > amount ? -1 : dp[amount];
    }
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);   // dp[a] = fewest coins for amount a
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity); // dp[a] = fewest coins for amount a
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (1-D).