Coin Change

MediumAmazonGoogleMicrosoftMeta

Problem

Given an integer array coins representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. Return -1 if impossible.

Intuition — the key insight

dp[i] = minimum coins to make amount i. For each amount, try every coin: if we use coin c, the remaining amount is i-c which we already know the answer to. So dp[i] = min(dp[i-c] + 1) for all valid coins c.

Approach

1. Define dp array

dp[0] = 0 (0 coins for amount 0). dp[1..amount] = Infinity initially (not yet reachable).

2. Fill bottom-up

For each amount i from 1 to target: for each coin c where c ≤ i: dp[i] = min(dp[i], dp[i-c] + 1).

3. Return result

dp[amount] is the answer. If still Infinity, return -1.

Complexity

Time

O(amount × coins)

Space

O(amount)

Outer loop runs amount times, inner loop runs once per coin. dp array has amount+1 entries.

Solution code

Python

def coinChange(self, coins: List[int], amount: int) -> int:
    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

Edge cases to remember

⚠Amount = 0: return 0

⚠No combination possible: return -1

⚠Single coin equals amount: return 1

⚠Using amount+1 as infinity avoids overflow compared to INT_MAX + 1

Hints

What pattern do you think this problem uses?