22  Coin Change

Rank 20 · Pattern: one-dimensional bottom-up dynamic programming · Target: \(O(amount\times coins)\) time

22.1 Problem definition

Given an array of coin denominations and a target amount, return the minimum number of coins needed to total that amount, or the language’s conventional absence result when no exact total is possible.

22.2 Clarifying questions

1. May each denomination be used more than once?
2. What constraints apply to the denominations and amount?
3. Is the task to minimize the number of coins, count combinations, or return the coins themselves?
4. What should I return when the amount is impossible or is zero?
5. Can the denomination array be empty or null?

22.3 Sample answers

1. Yes. Each denomination may be used an unlimited number of times.
2. amount is nonnegative, and every denomination is a positive integer.
3. Return only the minimum coin count.
4. Return -1 in Java/Python or None in Rust when no exact total is possible, and return zero coins for amount 0.
5. The array is non-null. It may be empty; then only amount 0 is possible.

22.4 Data structure and DP state

fewest has one entry per amount from 0 through the target.

Java

Use an int[]; each positive entry is initialized as its outer-loop iteration begins.

Python

Use a list initialized as [0] + [impossible] * amount.

Rust

Use Vec<usize> for nonnegative amounts and counts. The public result is Option<usize>, avoiding a negative sentinel at the API boundary.

State definition: fewest[x] is the minimum coins needed to make exactly x, among amounts already computed.

Base case: fewest[0] = 0. Before computing each positive amount, initialize that entry to the sentinel amount + 1. The sentinel is worse than any real answer because no valid solution needs more than amount positive coins when denomination 1 exists.

The recurrence considers the final coin:

\[ fewest[x] = \min_{coin \le x}(fewest[x-coin] + 1) \]

22.5 Approach and invariant

Greedily taking the largest coin is not generally correct: with coins [1,3,4] and amount 6, greedy uses 4+1+1 while the optimum is 3+3.

Compute amounts in increasing order. For each current amount, try every coin that fits. All referenced smaller states are already final.

For coins [1,2,5] through amount 6:

amount	0	1	2	3	4	5	6
fewest	0	1	1	2	2	1	2

For amount 6, the candidates include fewest[5]+1 = 2, fewest[4]+1 = 3, and fewest[1]+1 = 2.

Invariant: before computing current, every fewest[x] for x < current is the true optimum or the impossible sentinel.

22.6 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class CoinChangeSolution {
    static int coinChange(int[] coins, int amount) {
        int impossible = amount + 1;
        int[] fewest = new int[amount + 1];
        fewest[0] = 0;

        for (int current = 1; current <= amount; current++) {
            fewest[current] = impossible;
            for (int coin : coins) {
                if (coin <= current) {
                    fewest[current] = Math.min(fewest[current],
                                               fewest[current - coin] + 1);
                }
            }
        }
        if (fewest[amount] == impossible) {
            return -1;
        }
        return fewest[amount];
    }

    @Test public void findsMinimumNumberOfCoins() {
        assertEquals(3, coinChange(new int[] {1, 2, 5}, 11));
    }

    @Test public void reportsImpossibleAmount() {
        assertEquals(-1, coinChange(new int[] {2}, 3));
    }

    @Test public void zeroAmountNeedsNoCoins() {
        assertEquals(0, coinChange(new int[0], 0));
    }

    @Test public void exactDenominationNeedsOneCoin() {
        assertEquals(1, coinChange(new int[] {5}, 5));
    }

    @Test public void reusesDenominationWithoutLimit() {
        assertEquals(3, coinChange(new int[] {2}, 6));
    }

    @Test public void greedyChoiceCanFail() {
        assertEquals(2, coinChange(new int[] {1, 3, 4}, 6));
    }

    @Test public void ignoresCoinLargerThanAmount() {
        assertEquals(-1, coinChange(new int[] {5}, 3));
    }

    @Test public void handlesNoCoins() {
        assertEquals(-1, coinChange(new int[0], 3));
    }

    public static void main(String[] args) {
        JUnitCore.main("CoinChangeSolution");
    }
}

Python

import unittest


def coin_change(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount

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

    return -1 if fewest[amount] == impossible else fewest[amount]


class CoinChangeTests(unittest.TestCase):
    def test_finds_minimum_number_of_coins(self):
        self.assertEqual(3, coin_change([1, 2, 5], 11))

    def test_reports_impossible_amount(self):
        self.assertEqual(-1, coin_change([2], 3))

    def test_zero_amount_needs_no_coins(self):
        self.assertEqual(0, coin_change([], 0))

    def test_exact_denomination_needs_one_coin(self):
        self.assertEqual(1, coin_change([5], 5))

    def test_reuses_denomination_without_limit(self):
        self.assertEqual(3, coin_change([2], 6))

    def test_greedy_choice_can_fail(self):
        self.assertEqual(2, coin_change([1, 3, 4], 6))

    def test_ignores_coin_larger_than_amount(self):
        self.assertEqual(-1, coin_change([5], 3))

    def test_handles_no_coins(self):
        self.assertEqual(-1, coin_change([], 3))


if __name__ == "__main__":
    unittest.main()

Rust

pub fn coin_change(coins: &[usize], amount: usize) -> Option<usize> {
    let impossible = amount + 1;
    let mut fewest = vec![impossible; amount + 1];
    fewest[0] = 0;

    for current in 1..=amount {
        for &coin in coins {
            if coin <= current {
                fewest[current] = fewest[current].min(fewest[current - coin] + 1);
            }
        }
    }

    (fewest[amount] != impossible).then_some(fewest[amount])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn finds_minimum_number_of_coins() {
        assert_eq!(Some(3), coin_change(&[1, 2, 5], 11));
    }

    #[test]
    fn reports_impossible_amount() {
        assert_eq!(None, coin_change(&[2], 3));
    }

    #[test]
    fn zero_amount_needs_no_coins() {
        assert_eq!(Some(0), coin_change(&[], 0));
    }

    #[test]
    fn exact_denomination_needs_one_coin() {
        assert_eq!(Some(1), coin_change(&[5], 5));
    }

    #[test]
    fn reuses_denomination_without_limit() {
        assert_eq!(Some(3), coin_change(&[2], 6));
    }

    #[test]
    fn greedy_choice_can_fail() {
        assert_eq!(Some(2), coin_change(&[1, 3, 4], 6));
    }

    #[test]
    fn handles_no_coins() {
        assert_eq!(None, coin_change(&[], 3));
    }
}

Because impossible = amount + 1, the sentinel is worse than any valid answer and cannot be mistaken for a minimum.

22.7 High-value tests

Coins / amount	Expected	Purpose
[1,2,5] / 11	3	ordinary optimum
[2] / 3	absent	unreachable
[2,5] / 0	0	base case
[1,3,4] / 6	2	greedy counterexample
[5] / 5	1	exact denomination
coin larger than amount	ignored	boundary
[] / 3	absent	no denominations

22.8 Complexity and correctness

Let \(a\) be the amount and \(c\) the number of denominations. The nested loops cost \(O(ac)\) time and the table uses \(O(a)\) space.

Any optimal solution for positive amount x ends with some coin coin; removing it leaves an optimal solution for x - coin—otherwise replacing that prefix would improve the original. Trying every possible final coin and taking the minimum therefore yields the optimum. Increasing computation order guarantees every dependency is ready.

22.9 If the interviewer pushes

• Return the actual coins by storing which coin last improved each amount, then backtrack from the target.
• A top-down memoized recursion has the same asymptotic bounds and may follow fewer reachable states, but uses call-stack space.
• A BFS over reachable amounts also finds the fewest coins because each edge adds one coin.
• Filter nonpositive denominations; a zero or negative coin violates the recurrence’s progress assumption.
• If the question asks for the number of combinations, the DP meaning and loop ordering change substantially.

22.10 TDD interview script

Confirm unlimited reuse of positive denominations, nonnegative amount, minimum count rather than combinations, zero coins for amount zero, the language’s absence result when impossible, and a possibly empty valid coin collection. Then write this test list:

1. Zero amount
2. Exact coin
3. Repeated denomination use
4. Impossible amount
5. Ordinary optimum
6. Greedy counterexample
7. Oversized coin
8. No coins

Use one red–green–refactor cycle per behavior. State the DP state before creating the table, confirm the test fails for the intended reason, add the smallest base case or recurrence change, and rerun the complete example. Assert only the minimum count, not table entries.

From book/src, run:

Java

./java/run.sh CoinChangeSolution

Python

./python/run.sh coin_change_solution

Rust

./rust/run.sh coin_change_solution

When the greedy counterexample arrives, explain that the recurrence tries every possible final coin. Computing target amounts in increasing order ensures the optimal smaller amount is already known.

22.10.1 Pseudocode

impossible = amount + 1
fewest = array indexed 0 through amount
fewest[0] = 0

for current from 1 through amount:
    fewest[current] = impossible
    for each coin:
        if coin <= current:
            fewest[current] = min(
                fewest[current],
                fewest[current - coin] + 1
            )

return the language's absence result if fewest[amount] is impossible
otherwise return fewest[amount]

Before computing current, every smaller table entry is its true optimum or the impossible sentinel. Every candidate represents choosing coin last.

22.10.2 TDD sequence

Step	Test code added	Production code added or changed
1. Zero base case	zeroAmountNeedsNoCoins	Allocate through index zero, set fewest[0] = 0, and return it without needing a denomination.
2. Exact coin	exactDenominationNeedsOneCoin	For each amount, try fitting coins and set the candidate to the smaller state’s result plus one.
3. Unlimited reuse	reusesDenominationWithoutLimit	Compute amounts in increasing order so the same denomination can extend previously solved states repeatedly.
4. Impossible state	reportsImpossibleAmount	Initialize positive states to an amount + 1 sentinel and translate an unchanged target sentinel to -1.
5. Competing choices	findsMinimumNumberOfCoins	Try every denomination for every amount and retain the minimum candidate.
6. Greedy regression	greedyChoiceCanFail	Confirm the DP compares complete alternatives and selects 3 + 3 over a largest-coin-first result.
7. Coin does not fit	ignoresCoinLargerThanAmount	Guard coin <= current before indexing fewest[current - coin].
8. No transitions	handlesNoCoins	Leave positive states impossible when the denomination loop is empty.

The sequence derives bottom-up DP from its base case and recurrence, then uses the greedy counterexample as a targeted algorithm-choice regression rather than merely another input.