Coin Change

This one looks friendly. You have some coins, you have an amount, and you just need to pay it with the fewest coins. Easy, right? But the interviewer is not testing your math. They want to see if you reach for the obvious greedy idea and then notice it can give a wrong answer. The real test is whether you can build the answer step by step from smaller answers. That is dynamic programming. It means we solve tiny versions first and reuse them to solve the big one.

🪙 The Problem

You are given a list of coin denominations and a target amount. A denomination is just the value printed on a coin, like 1, 2 or 5. You can use each coin as many times as you want. Return the fewest number of coins that add up to the amount. If no combination works, return -1.

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

Input:  coins = [2], amount = 3
Output: -1
Explanation: With only 2-coins you can never make an odd amount.

🤔 The Greedy Trap

The first idea most people have is greedy. Greedy means you always grab the biggest coin that still fits, then repeat. For coins = [1, 2, 5] and amount 11 it works fine. Take 5, take 5, take 1. Three coins.

But now try coins = [1, 3, 4] and amount 6. Greedy grabs the biggest coin 4 first. Then 6 - 4 = 2, so it takes 1 and 1. That is three coins total. But the real best answer is 3 + 3, which is only two coins. So greedy can miss the best answer. That is exactly the mistake the interviewer wants to catch.

So we need something that checks all the options, not just the biggest coin. That is where dynamic programming comes in.

💡 The DP Idea

Here is the trick. Suppose I already know the fewest coins for every amount smaller than my target. Then for the target amount, I just try each coin. If I use one coin, the rest of the bill is amount - coin, and I already know the best answer for that smaller amount. So the answer for amount is one coin plus the best answer for amount - coin. I try every coin and keep the smallest.

We store these answers in an array called dp. So dp[a] means the fewest coins needed to make amount a. The rule is:

dp[a] = 1 + min( dp[a - coin] )   for every coin that fits in a

We start from 0 and fill the table upward until we reach the amount. We set dp[0] = 0 because making amount zero needs no coins. Every other slot starts as “impossible”, a very big number, so we know it is not reachable yet.

Let us fill the table for coins = [1, 2, 5] and amount 6. Read it slot by slot.

dp[0] = 0      (zero coins)
dp[1] = 1      (one 1-coin)
dp[2] = 1      (one 2-coin)
dp[3] = 2      (2 + 1)
dp[4] = 2      (2 + 2)
dp[5] = 1      (one 5-coin)
dp[6] = 2      (5 + 1)

See how each slot is built from an earlier, smaller slot? That is the whole idea. The final slot dp[6] holds our answer: 2.

📝 Steps to Solve

1. Make a dp array of size amount + 1. Set every slot to a big “impossible” value.
2. Set dp[0] = 0, since zero amount needs zero coins.
3. Loop a from 1 up to amount. This is the amount we are solving right now.
4. For each a, try every coin. If coin is not bigger than a and dp[a - coin] is reachable, then dp[a] can become dp[a - coin] + 1. Keep the smallest such value.
5. At the end, if dp[amount] is still the big “impossible” value, return -1. Otherwise return dp[amount].

#include <stdio.h>
#include <limits.h>

// Returns the fewest coins for 'amount', or -1 if impossible.
int coinChange(int coins[], int n, int amount) {
    int big = amount + 1;          // a value larger than any real answer
    int dp[amount + 1];
    for (int a = 0; a <= amount; a++) dp[a] = big;
    dp[0] = 0;                     // zero amount needs zero coins

    for (int a = 1; a <= amount; a++) {
        for (int i = 0; i < n; i++) {
            if (coins[i] <= a && dp[a - coins[i]] + 1 < dp[a]) {
                dp[a] = dp[a - coins[i]] + 1;
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

int main(void) {
    int coins[] = {1, 2, 5};
    printf("%d\n", coinChange(coins, 3, 11));
    int coins2[] = {2};
    printf("%d\n", coinChange(coins2, 1, 3));
    return 0;
}

3
-1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Returns the fewest coins for 'amount', or -1 if impossible.
int coinChange(vector<int>& coins, int amount) {
    int big = amount + 1;              // larger than any real answer
    vector<int> dp(amount + 1, big);
    dp[0] = 0;                         // zero amount needs zero coins

    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a) {
                dp[a] = min(dp[a], dp[a - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    cout << coinChange(coins, 11) << endl;
    vector<int> coins2 = {2};
    cout << coinChange(coins2, 3) << endl;
    return 0;
}

3
-1

import java.util.Arrays;

public class CoinChange {
    // Returns the fewest coins for 'amount', or -1 if impossible.
    static int coinChange(int[] coins, int amount) {
        int big = amount + 1;            // larger than any real answer
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, big);
        dp[0] = 0;                       // zero amount needs zero coins

        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];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
        System.out.println(coinChange(new int[]{2}, 3));
    }
}

3
-1

def coin_change(coins, amount):
    big = amount + 1                      # larger than any real answer
    dp = [big] * (amount + 1)
    dp[0] = 0                             # zero amount needs zero coins

    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]


print(coin_change([1, 2, 5], 11))
print(coin_change([2], 3))

3
-1

// Returns the fewest coins for 'amount', or -1 if impossible.
function coinChange(coins, amount) {
  const big = amount + 1;                 // larger than any real answer
  const dp = new Array(amount + 1).fill(big);
  dp[0] = 0;                              // zero amount needs zero coins

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11));
console.log(coinChange([2], 3));

3
-1

⏱️ Time and Space Complexity

The greedy approach is fast but it gives wrong answers for some coin sets, so it does not really count as a solution. The DP approach is the one to bring to the interview.

The DP time is amount slots, and for each slot we try every coin. So it is the amount multiplied by the number of coins. The space is just the one dp array, which has amount + 1 slots.

🧩 Key Takeaways

• ✅ Greedy can fail here, so reach for DP. Always have the [1, 3, 4] counter-example ready.
• ✅ dp[a] is the fewest coins for amount a, and dp[a] = 1 + min(dp[a - coin]) over the coins that fit.
• ✅ Fill the table from 0 upward so every smaller answer is ready before you need it.
• ✅ Start slots at a big “impossible” value and set dp[0] = 0.
• ✅ At the end, an untouched dp[amount] means the amount is impossible, so return -1.
• ✅ Time is O(amount × coins) and space is O(amount).

🚀 What’s Next?

• House Robber
• Introduction to Dynamic Programming