Coin Change

You are given a list coins of distinct coin values and a total amount. You have an unlimited supply of every coin value.

Return the smallest number of coins whose values add up to exactly amount. If no combination of coins can make that total, return -1. Making an amount of 0 needs no coins at all, so the answer for it is 0.

Example 1

Example 2

Example 3

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• All coin values are distinct.
• 0 <= amount <= 104

Pattern Path · Dynamic Programming · problem 148 of 169

Start simple

Recursively try every coin as the next coin for the remaining amount: exponential time, because the same remaining amounts are solved again and again.

The key idea

Greedy fails because a large coin can leave a remainder that is expensive to finish. Instead, think about the last coin in an optimal solution for x. If its value is c, the remaining coins form an optimal solution for x - c (otherwise you could swap in a better one). So the best count for x is one more than the best count among all x - c.

That recurrence only looks at smaller amounts, so fill a table best[0..amount] in increasing order. Start with best[0] = 0 and every other entry as "unreachable" (any value bigger than amount works, since you can never need more than amount coins). For each x, try every coin that fits and keep the minimum of best[x - c] + 1. Amounts that no coin combination reaches stay unreachable, which becomes -1.

The table has amount + 1 entries and each one tries every coin, so the work is amount × number of coins. You can also see it as a shortest-path BFS where each coin is an edge of length one.

Complexity

• Time: O(amount · k), k = number of coins
• Space: O(amount)

Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        UNREACHABLE = amount + 1  # more coins than could ever be needed
        best = [0] + [UNREACHABLE] * amount

        for total in range(1, amount + 1):
            for coin in coins:
                if coin <= total:
                    best[total] = min(best[total], best[total - coin] + 1)

        return best[amount] if best[amount] != UNREACHABLE else -1

JavaScript

var coinChange = function(coins, amount) {
  const UNREACHABLE = amount + 1; // more coins than could ever be needed
  const best = new Array(amount + 1).fill(UNREACHABLE);
  best[0] = 0;

  for (let total = 1; total <= amount; total++) {
    for (const coin of coins) {
      if (coin <= total) {
        best[total] = Math.min(best[total], best[total - coin] + 1);
      }
    }
  }

  return best[amount] === UNREACHABLE ? -1 : best[amount];
};

What the interviewer is checking

This is the classic test of whether you recognise when greedy fails and can turn a recursive "try every last choice" idea into a bottom-up DP table.

Mistakes to avoid

• Assuming greedy (largest coin first) is optimal.
• Using infinity or a sentinel and then adding 1 to it, which can overflow in fixed-width languages; amount + 1 is a safe sentinel.
• Forgetting that amount = 0 should return 0, not -1.
• Huge coin values: compute x - c only when c <= x.

Follow-ups to expect

• How many different ways can you make the amount? (Loop coins outer, sum counts.)
• Can you also return which coins are used? (Store the last coin per amount.)
• What if each coin can be used only once? (0/1 knapsack, iterate amounts downward.)

In real software

Vending machines and cash registers that must pay out change, and systems that pack data into fixed block sizes with the fewest blocks, solve this unbounded-knapsack style problem.

Practice next