322. Coin Change (Medium)

Problem

Given coins of various denominations and a target amount, return the fewest number of coins summing to amount (or -1 if impossible). Coins may be used unlimited times.

Example

• coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)
• coins = [2], amount = 3 → -1
• coins = [1], amount = 0 → 0

LeetCode 322 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Recursive

f(n) = 1 + min(f(n - c) for c in coins if c ≤ n).

Python

def coin_change(coins, amount):
    def f(n):                                      # L1: define recursive helper
        if n == 0:                                 # L2: O(1) base case
            return 0
        if n < 0:                                  # L3: O(1) base case
            return float('inf')
        best = float('inf')                        # L4: O(1)
        for c in coins:                            # L5: loop over |coins| denominations
            best = min(best, 1 + f(n - c))        # L6: O(1) + recurse
        return best
    result = f(amount)                             # L7: kick off recursion
    return -1 if result == float('inf') else result  # L8: O(1)

TypeScript

function coinChange(coins: number[], amount: number): number {
    function f(n: number): number {                            // L1: define recursive helper
        if (n === 0) return 0;                                // L2: O(1) base case
        if (n < 0) return Infinity;                           // L3: O(1) base case
        let best = Infinity;                                  // L4: O(1)
        for (const c of coins) {                             // L5: loop over denominations
            best = Math.min(best, 1 + f(n - c));             // L6: O(1) + recurse
        }
        return best;
    }
    const result = f(amount);                                // L7: kick off recursion
    return result === Infinity ? -1 : result;                // L8: O(1)
}

Swift

final class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int { func solve(_ remaining: Int) -> Int { if remaining == 0 { return 0 }; if remaining < 0 { return Int.max / 4 }; let best = coins.map { solve(remaining - $0) }.min() ?? Int.max / 4; let result = best >= Int.max / 4 ? best : best + 1; return result }; let answer = solve(amount); return answer >= Int.max / 4 ? -1 : answer }
}

Where the time goes, line by line

Variables: n = len(coins), A = the target amount.

Line	Per-call cost	Times executed	Contribution
L2, L3 (base cases)	$O(1)$	once per call	$O(1)$ each
L5 (coin loop)	$O(1)$	n per call	$O(n)$ per call
L6 (recurse)	$O(n)$ per branch	branches up to n^A	$O(n · n^A)$ ← dominates

Without memoization every sub-problem is recomputed from scratch. The call tree has up to n choices at each of A levels, giving an exponential blowup.

Complexity

• Time: $O(n^A)$, driven by L6. Exponential, unusable.
• Space: $O(A)$ for the recursion stack.

Approach 2: Top-down memoized

Python

from functools import lru_cache

def coin_change(coins, amount):
    @lru_cache(maxsize=None)
    def f(n):                                      # L1: define memoized helper
        if n == 0:                                 # L2: O(1) base case
            return 0
        if n < 0:                                  # L3: O(1) base case
            return float('inf')
        best = float('inf')                        # L4: O(1)
        for c in coins:                            # L5: loop over n denominations
            best = min(best, 1 + f(n - c))        # L6: O(1) + cached sub-call
        return best
    result = f(amount)                             # L7: kick off recursion
    return -1 if result == float('inf') else result  # L8: O(1)

TypeScript

function coinChange(coins: number[], amount: number): number {
    const memo = new Map<number, number>();
    function f(n: number): number {                            // L1: define memoized helper
        if (n === 0) return 0;                                // L2: O(1) base case
        if (n < 0) return Infinity;                           // L3: O(1) base case
        if (memo.has(n)) return memo.get(n)!;
        let best = Infinity;                                  // L4: O(1)
        for (const c of coins) {                             // L5: loop over n denominations
            best = Math.min(best, 1 + f(n - c));             // L6: O(1) + cached sub-call
        }
        memo.set(n, best);
        return best;
    }
    const result = f(amount);                                // L7: kick off recursion
    return result === Infinity ? -1 : result;                // L8: O(1)
}

Swift

final class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int { var memo: [Int: Int] = [:]; func solve(_ remaining: Int) -> Int { if remaining == 0 { return 0 }; if remaining < 0 { return Int.max / 4 }; if let v = memo[remaining] { return v }; let best = coins.map { solve(remaining - $0) }.min() ?? Int.max / 4; let result = best >= Int.max / 4 ? best : best + 1; memo[remaining] = result; return result }; let answer = solve(amount); return answer >= Int.max / 4 ? -1 : answer }
}

Where the time goes, line by line

Variables: n = len(coins), A = the target amount.

Line	Per-call cost	Times executed	Contribution
L2, L3 (base cases)	$O(1)$	once per unique n	$O(A)$ total
L5, L6 (coin loop)	$O(n)$ per unique call	A unique values of n	$O(n · A)$ ← dominates
L7 (initial call)	$O(1)$	1	$O(1)$

Each value from 0 to A is computed exactly once. The coin loop inside each call is $O(n)$. Cache lookup and store are $O(1)$ amortized.

Complexity

• Time: $O(n · A)$, driven by L5/L6.
• Space: $O(A)$ for the memo table plus $O(A)$ for the call stack.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Bottom-up DP (canonical)

dp[i] = min coins to make i. dp[0] = 0; dp[i] = min(dp[i - c] + 1) over valid coins.

Python

def coin_change(coins, amount):
    INF = amount + 1                               # L1: sentinel larger than any valid answer
    dp = [INF] * (amount + 1)                     # L2: O(A) init
    dp[0] = 0                                      # L3: base case
    for i in range(1, amount + 1):                 # L4: outer loop, A iterations
        for c in coins:                            # L5: inner loop, n iterations
            if c <= i:                             # L6: O(1) guard
                dp[i] = min(dp[i], dp[i - c] + 1) # L7: O(1) recurrence
    return dp[amount] if dp[amount] != INF else -1 # L8: O(1)

TypeScript

function coinChange(coins: number[], amount: number): number {
    const INF = amount + 1;                                    // L1: sentinel
    const dp = new Array(amount + 1).fill(INF);               // L2: O(A) init
    dp[0] = 0;                                                // L3: base case
    for (let i = 1; i <= amount; i++) {                      // L4: outer loop, A iterations
        for (const c of coins) {                             // L5: inner loop, n iterations
            if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);  // L6/L7: O(1) recurrence
        }
    }
    return dp[amount] !== INF ? dp[amount] : -1;             // L8: O(1)
}

Swift

final class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int { var dp = Array(repeating: amount + 1, count: amount + 1); dp[0] = 0; if amount > 0 { for value in 1...amount { for coin in coins where coin <= value { dp[value] = min(dp[value], dp[value - coin] + 1) } } }; return dp[amount] > amount ? -1 : dp[amount] }
}

Where the time goes, line by line

Variables: n = len(coins), A = the target amount.

Line	Per-call cost	Times executed	Contribution
L2 (init dp)	$O(1)$	A+1	$O(A)$
L3 (base case)	$O(1)$	1	$O(1)$
L4 (outer loop)	$O(1)$	A	$O(A)$
L5, L7 (inner loop + recurrence)	$O(1)$	A · n	$O(A · n)$ ← dominates
L8 (return)	$O(1)$	1	$O(1)$

The double loop at L4/L5 is the whole story. Every (amount, coin) pair is visited exactly once, and L7 is $O(1)$ table lookup plus comparison. No inner recursion, no re-scanning; the DP order guarantees dp[i - c] is already filled when we need it.

Complexity

• Time: $O(A · n)$, driven by L5/L7 (the double loop).
• Space: $O(A)$ for the dp table.

Unbounded vs. 0/1 knapsack

Coin Change is unbounded, each coin can be used infinitely. The outer loop over amounts lets the DP “re-use” a coin naturally. Compare with 0/1 knapsack (problem 416 Partition Equal Subset Sum), where each item is used at most once and loop order matters.

The sentinel choice

INF = amount + 1 works because you can never need more than amount coins of denomination 1. Any reachable amount costs at most amount coins, so amount + 1 is guaranteed larger than any valid answer. The min() recurrence will always prefer a real path over the sentinel, and the final check dp[amount] != INF cleanly separates reachable from unreachable.

float('inf') works too, but amount + 1 stays an integer and gives a tighter bound. See Sentinel Values for the general pattern across DP, shortest-path, and search problems.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Naive recursion	$O(n^A)$	$O(A)$
Top-down memo	$O(A · n)$	$O(A)$
Bottom-up DP	$O(A · n)$	$O(A)$

Template for “min operations to reach target” under free reuse: Coin Change, Perfect Squares, Minimum Cost For Tickets.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_322.py and run.
# Uses the canonical implementation (Approach 3: Bottom-up DP).

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

def _run_tests():
    assert coin_change([1, 2, 5], 11) == 3      # 5+5+1, LeetCode example
    assert coin_change([2], 3) == -1             # impossible
    assert coin_change([1], 0) == 0              # zero amount
    assert coin_change([1], 1) == 1              # single coin exact match
    assert coin_change([2, 5, 10, 1], 27) == 4  # 10+10+5+2
    assert coin_change([186, 419, 83, 408], 6249) == 20
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function coinChange(coins: number[], amount: number): number {
    const INF = amount + 1;
    const dp = new Array(amount + 1).fill(INF);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (const c of coins) {
            if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
        }
    }
    return dp[amount] !== INF ? dp[amount] : -1;
}

console.assert(coinChange([1, 2, 5], 11) === 3);
console.assert(coinChange([2], 3) === -1);
console.assert(coinChange([1], 0) === 0);
console.assert(coinChange([1], 1) === 1);
console.assert(coinChange([2, 5, 10, 1], 27) === 4);
console.assert(coinChange([186, 419, 83, 408], 6249) === 20);
console.log('all tests pass');

Related topics

• Arrays, DP table indexed by amount
• Sentinel Values, the general pattern for “impossible” placeholders in algorithms

Related concepts

• Dynamic Programming, state-and-transition tactics for solving overlapping subproblems with cached answers.
• Knapsack Patterns, choose-or-skip DP tactics for capacity, subset, and target-sum problems.
• Tabulation, bottom-up DP tactics for filling states in dependency order without recursion.