Skip to content

136 — Coin Change

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

136 — Coin Change

LeetCode 322 · Medium. You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1. You may assume there are infinitely many coins of each denomination.

🍽️ Intuition

Picture trying to make change for amount cents. Whatever the first coin you reach for is, using it leaves you needing the fewest coins to make up amount - coin — a strictly smaller version of the exact same problem. So the fewest coins to make amount is just 1 (for the coin you just used) plus the fewest coins to make the leftover, minimized over every denomination you could have started with. The only twist versus House Robber-style DP is that the lookback window isn't a small fixed number of positions — it's determined by however many coin denominations there are, and any of them can be reused as many times as needed.

🚩 Pattern-Recognition Cue

"Fewest number of coins to make up an amount, coins reusable without limit" is the unbounded-knapsack tell: dp[i] (the answer for amount i) depends on dp[i - coin] for every denomination coin, and because coins can repeat, the recurrence reaches back by a variable amount (one full denomination) rather than a fixed window of one or two positions.

🐢 Brute Force

Recurse from the full amount, trying every coin as "the next coin used," with no memoization — the same leftover amounts get reached (and re-solved) via many different coin combinations.

func coinChangeBruteForce(_ coins: [Int], _ amount: Int) -> Int {
    func minCoinsFrom(_ remaining: Int) -> Int {
        if remaining == 0 { return 0 }
        if remaining < 0 { return Int.max }

        var best = Int.max
        for coin in coins {
            let sub = minCoinsFrom(remaining - coin)
            if sub != Int.max {
                best = min(best, sub + 1)
            }
        }
        return best
    }

    let result = minCoinsFrom(amount)
    return result == Int.max ? -1 : result
}

// smoke test
print(coinChangeBruteForce([1, 2, 5], 11))   // 3  (5 + 5 + 1)
print(coinChangeBruteForce([2], 3))          // -1 (odd amount, only even coins)
print(coinChangeBruteForce([1], 0))          // 0

Big-O: O(k^amount) time in the worst case, where k is the number of denominations — every level of recursion branches k ways, and the same leftover amounts are re-solved independently from every combination of coins that reaches them. O(amount) space for the recursion stack.

🚀 Optimal

Tabulate the fewest-coins answer for every amount from 0 up to the target, using an "unreachable" sentinel (amount + 1, larger than any possible real answer) instead of Int.max so additions never overflow.

func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    guard amount > 0 else { return 0 }

    var dp = Array(repeating: amount + 1, count: amount + 1)   // amount + 1 = "unreachable"
    dp[0] = 0

    for i in 1...amount {
        for coin in coins where coin <= i {
            dp[i] = min(dp[i], dp[i - coin] + 1)
        }
    }

    return dp[amount] > amount ? -1 : dp[amount]
}

// smoke test — same cases as the brute force
print(coinChange([1, 2, 5], 11))   // 3
print(coinChange([2], 3))          // -1
print(coinChange([1], 0))          // 0

Big-O: O(amount · k) time, where k is the number of denominations — for each of the amount sub-totals, try each of the k coins once. O(amount) space for the dp array.

🔑 The Key Insight

Both versions consider the exact same choice at every amount — try each denomination as "the last coin used," and recurse on the leftover — but the brute force treats every leftover amount as a brand-new problem no matter how many different coin combinations arrive at it, so the same sub-totals get re-solved exponentially many times. The optimal version tabulates every amount from 0 up to the target exactly once, in order, so that by the time amount i is being computed, dp[i - coin] for every denomination is already a finished, reusable answer rather than something to re-derive. Reusing k already-solved smaller answers per amount, instead of re-branching k ways from scratch, is what turns exponential coin combinations into a flat O(amount · k) table fill.

🔗 Related Chapters

  • 1D Dynamic Programming — chapter 26 calls this out directly: unlike House Robber's fixed two-state lookback, dp[i] here depends on dp[i - coin] for as many earlier states as there are denominations, one lookback per coin value rather than a fixed small window.
  • Arrays and Strings — dp is filled left to right in a single array, the same tabulation-array pattern used across every 1-D DP problem in this batch.

🧸 Memory Sentence

Coin Change is unbounded knapsack in miniature — the fewest coins to make amount i is one plus the fewest coins to make i - coin, minimized over every denomination, with each amount's answer computed once and reused by every larger amount that needs it.

✅ Check Your Understanding

  1. Why is amount + 1 used as the "unreachable" sentinel instead of Int.max? What would go wrong at the line dp[i] = min(dp[i], dp[i - coin] + 1) if dp[i - coin] were Int.max?
  2. Trace coinChange([1, 2, 5], 11) far enough to explain why dp[11] ends up as 3 rather than, say, 11 (eleven 1-coins) or some other valid-but-worse combination.
  3. The inner loop uses for coin in coins where coin <= i instead of checking the bound inside the loop body. Why is skipping coins larger than i necessary for correctness, not just an optimization?

⬅️ Previous: Decode Ways · Next: Maximum Product Subarray ➡️

Clone this wiki locally