Coin Change

PracticeNeetCode ↗LeetCode ↗

Given coin denominations coins (unlimited supply of each) and a target amount, return the fewest coins needed to make that amount. If it can't be made, return -1.

Example

Key Pointers

• Bottom-up DP: the fewest coins to make amount a is 1 + the fewest coins to make (a − coin), minimized over every coin that's ≤ a.
• Seed the DP array with a sentinel larger than any real answer (amount + 1) so "unreachable" amounts stay distinguishable from genuine answers until the very end.
• dp[0] = 0 is the essential base case — zero coins make an amount of zero.

Step-by-Step Analysis

1. Create dp, an array of size amount + 1, filled with the sentinel amount + 1, then set dp[0] = 0.
2. For each target a from 1 to amount: for every coin ≤ a, update dp[a] = min(dp[a], 1 + dp[a - coin]).
3. Once the table is filled, dp[amount] holds either the true minimum or the untouched sentinel.
4. Return dp[amount] if it isn't the sentinel, otherwise -1.

Complexity

Time: O(amount · len(coins)) — Space: O(amount)

Code

def coinChange(coins: list[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

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

    return dp[amount] if dp[amount] != amount + 1 else -1

Code Explanation

How the solution above works, piece by piece.

1. dp[a] = the fewest coins that sum to a. It starts at amount + 1, an impossible count that acts as infinity.
2. dp[0] = 0: zero coins make zero.
3. For each amount, try ending with each coin: 1 + dp[a - coin] uses one coin plus the best way to make the rest.
4. Smaller amounts are filled first, so dp[a - coin] is always ready when needed.
5. If dp[amount] is still the sentinel, it can't be made → −1. O(amount × coins) time.

Visual Walkthrough

Running it on coins = [1, 2, 5], amount = 11:

Video Explanation

NeetCode — Coin Change, Bottom-Up DP, LeetCode 322