MediumDynamic ProgrammingBreadth-First SearchUpdated Sep 2026

322. Coin Change

Asked at Google, Meta, Amazon, Microsoft and 4 more

Difficulty

Medium

Time

O(amount × coins)

Space

O(amount)

Pattern

Dynamic Programming

Companies

8

Problem

You are given coin denominations and a target amount. Return the fewest coins that add up to that amount, or -1 if no combination of the coins can reach it.

You have an unlimited supply of every denomination, and you can use the same coin as many times as you like.

Fewest coins, not any coins

one way to make 115513 coins — this is the minimumanother way52224 coins — valid, but not the answer
Greedy "take the biggest coin first" happens to work here, but it breaks on coin sets like [1,3,4] for amount 6.

Constraints

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

Examples

Example 1
Inputcoins = [1,2,5], amount = 11
Output3
Why11 = 5 + 5 + 1. No combination of these coins reaches 11 with fewer than 3 coins.
Example 2
Inputcoins = [2], amount = 3
Output-1
WhyEvery amount you can build with 2s is even, so 3 is impossible.
Example 3
Inputcoins = [1], amount = 0
Output0
WhyReaching 0 takes no coins at all.

Asked At

8 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
UberMediumView all Uber questions →
WalmartMediumView all Walmart questions →
PinterestMediumView all Pinterest questions →

How to Think About It

1

This is an unbounded knapsack variant. You can use each coin unlimited times. dp[i] = minimum coins to make amount i.

2

The recurrence: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin where coin <= i. You're checking "if I use this coin, how many more do I need?"

3

Base case: dp[0] = 0 (zero coins needed for amount 0). Fill dp[1] through dp[amount] left to right.

4

Why bottom-up works: to compute dp[i], you need dp[i-coin] which is a smaller amount. By filling left to right, smaller amounts are always computed first.

5

Edge cases: amount=0 (return 0), no valid combination (return -1), single coin denomination.

Optimal Approach

Step 1: Create dp array of size amount+1, fill with infinity. dp[0] = 0.
Step 2: For i from 1 to amount:
For each coin where coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
Step 3: Return dp[amount] if not infinity, else -1.

The logic: if you use a coin of value "coin", you need 1 coin plus however many coins were needed for amount "i - coin".

Time: O(amount × number of coins). Space: O(amount).

Build the table from 0 upward

dp for coins = [1,2,5]01122122332301234567891011dp[11] = 3 — the answerdp[x] = min(dp[x], dp[x − coin] + 1)dp[0] = 0, everything else starts at infinitystill infinity at the end → return −1
dp[x] is the fewest coins for amount x. Each entry reuses answers that are already final.
ComplexityTime O(amount × coins)Space O(amount)One dp entry per amount, and every coin is tried against each one.

What Trips People Up in Real Interviews

1

Confusing "minimum coins" with "counting ways." This problem asks for the fewest coins, not the number of ways to make the amount.

2

Not handling the case where no combination works. Return -1, not 0 or null.

3

Forgetting to initialize dp[0] = 0. Zero coins are needed to make amount 0.

4

Using BFS instead of DP. BFS works (each level is one more coin) but DP is simpler and more efficient for this problem.

5

Filling the dp array in the wrong order. You must fill left to right (dp[0] to dp[amount]) because each dp[i] depends on smaller amounts (dp[i - coin]). Filling right to left gives wrong results.

Solution Code

O(amount × coins) time
def coinChange(coins, amount):
    dp = [float('inf')] * (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] != float('inf') else -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Coin Change problem?

You are given coins of different denominations and a total amount. Write a function to compute the fewest number of coins needed to make up that amount. If it is not possible, return -1.

How do you solve Coin Change?

The optimal approach runs in O(amount × coins) time and O(amount) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Coin Change?

Coin Change is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart, Pinterest. It is a medium difficulty problem.

What are common mistakes on Coin Change?
  • Confusing "minimum coins" with "counting ways." This problem asks for the fewest coins, not the number of ways to make the amount.
  • Not handling the case where no combination works. Return -1, not 0 or `null`.
  • Forgetting to initialize `dp[0]` = 0. Zero coins are needed to make amount 0.
  • Using BFS instead of DP. BFS works (each level is one more coin) but DP is simpler and more efficient for this problem.
  • Filling the dp array in the wrong order. You must fill left to right (`dp[0]` to `dp[amount]`) because each `dp[i]` depends on smaller amounts (`dp[i - coin]`). Filling right to left gives wrong results.