Free lesson · DSA Mastery - Interview Prep, End to End

Coin Change

Hard11 min readdsadynamic-programming

Coin Change

Coin Change is the canonical unbounded knapsack: given coin denominations and a target amount, find the minimum number of coins needed to make that amount, or report that it is impossible. The DP defines dp[a] = the fewest coins summing to amount a, with the transition dp[a] = min over each coin c of dp[a - c] + 1 (use one more coin of denomination c, on top of the best way to make a - c). Because coins are reusable, the capacity loop runs forward, letting dp[a - c] already include coin c. It establishes the minimize-count unbounded knapsack - the most common interview instance - and the handling of "impossible" amounts via an infinity sentinel that propagates correctly. We present bottom-up tabulation (canonical).

The insight: to make amount a with the fewest coins, consider what the last coin added was. If it was a coin of denomination c, then before adding it you had made a - c with the fewest coins (dp[a - c]), and adding this one coin gives dp[a - c] + 1. You do not know which last coin is best, so you try every denomination and take the minimum. Because each denomination has unlimited supply, dp[a - c] may itself already use coin c - which the forward loop permits, correctly modeling reuse.

The Problem

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 that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input:  coins = [1,2,5], amount = 11
Output: 3

Explanation: 11 = 5 + 5 + 1, using 3 coins.

Example 2:

Input:  coins = [2], amount = 3
Output: -1

Explanation: 3 cannot be made from only coins of denomination 2.

Constraints:

1 <= coins.length <= 12; 1 <= coins[i] <= 2^31 - 1; 0 <= amount <= 10^4.

Approaches Overview

#	Approach	Time	Space	Verdict
1	Bottom-up tabulation (forward, minimize count)	O(amount · #coins)	O(amount)	Canonical

dp[a] = the fewest coins summing to exactly a, or infinity if a is unreachable. Base case dp[0] = 0 (zero coins make amount 0). For each amount a from 1 to amount, try each coin c: if c <= a and dp[a - c] is reachable, then dp[a] = min(dp[a], dp[a - c] + 1). The forward loop over a allows reuse. The answer is dp[amount], or -1 if it remains infinity. Time O(amount · #coins); space O(amount).

Approach: Bottom-Up Tabulation - Canonical

The Idea

Define dp[a] = the minimum number of coins to make amount a, with dp[0] = 0 and all other entries initialized to a large sentinel (representing "unreachable"). Build dp from small amounts up. For each amount a, consider every coin c: if the coin fits (c <= a) and a - c is reachable, then making a by adding one coin c to the best way of making a - c costs dp[a - c] + 1. Take the minimum over all coins. After filling, dp[amount] is the answer, or -1 if it is still the sentinel.

Logic Flowchart

graph TD
    A["dp[0] = 0; dp[a] = INF for a >= 1"] --> B["for a from 1 to amount:"]
    B --> C["for each coin c:"]
    C --> D{"c <= a and dp[a-c] reachable?"}
    D -->|Yes| E["dp[a] = min(dp[a], dp[a-c] + 1)"]
    D -->|No| C
    E --> C
    C --> B
    B --> F{"dp[amount] still INF?"}
    F -->|Yes| G["return -1"]
    F -->|No| H["return dp[amount]"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Coin Change: a forward fill over amounts where each amount takes the minimum over coins of one plus the best for the remaining amount, returning negative one if the target stays unreachable.

Code

public static int coinChange(int[] coins, int amount) {
    int INF = amount + 1;                                // sentinel larger than any real answer
    int[] dp = new int[amount + 1];
    java.util.Arrays.fill(dp, INF);
    dp[0] = 0;                                           // zero coins make amount 0
    for (int a = 1; a <= amount; a++)                     // FORWARD over amount (reuse allowed)
        for (int c : coins)
            if (c <= a)
                dp[a] = Math.min(dp[a], dp[a - c] + 1);  // one more coin c on top of dp[a-c]
    return dp[amount] > amount ? -1 : dp[amount];        // still sentinel → impossible
}

// Usage:
// coinChange([1,2,5], 11) -> 3
// coinChange([2], 3) -> -1

This Java code solves Coin Change with forward tabulation: each amount's minimum coin count is one plus the best for the remaining amount over all coins, returning negative one if the target is unreachable.

Step-by-Step Walkthrough

Tracing coinChange([1,2,5], 11):

graph LR
    F0["dp[0]=0"]
    F1["dp[1]=1, dp[2]=1, dp[5]=1 (single coins)"]
    F2["dp[10]=2 (5+5), dp[11]=min(dp[10]+1, dp[9]+1, dp[6]+1)"]
    F3["dp[11] = 3 (5+5+1) → return 3"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough makes eleven from coins one, two, five: single coins seed the small amounts, ten is two fives, and eleven is five plus five plus one for three coins.

Result: 3.

Complexity

Time: O(amount · #coins) - for each amount, try each coin. Space: O(amount) for the dp array.

Complexity Comparison

Approach	Time	Space	Key Idea
Bottom-up tabulation	O(amount · #coins)	O(amount)	dp[a] = min over coins of dp[a-c] + 1; forward loop = reuse

The tabulation is the canonical solution. It is the minimize-count unbounded knapsack: the forward loop over amount allows each coin to be reused; the transition takes one more coin on top of the best way to make the remaining amount; and the infinity sentinel marks unreachable amounts, propagating so that a target that no coin combination can reach correctly returns -1.

Variations & Follow-ups

Why does the forward loop allow coin reuse, and how does this differ from 0/1?

The forward capacity loop is what makes Coin Change unbounded (coins reusable), and contrasting it with 0/1 knapsack's backward loop cements the distinction. In Coin Change, dp[a] is computed by trying each coin c and reading dp[a - c] - the best way to make the smaller amount a - c. Crucially, we iterate a forward (from 1 up to amount), so by the time we compute dp[a], the value dp[a - c] has already been finalized in this same pass and may itself use coin c. So adding one more c to dp[a - c] can stack multiple copies of c - e.g., dp[10] = 2 (two 5-coins) is built because dp[5] = 1 (one 5-coin) was computed earlier in the same forward pass, and dp[10] adds another 5. This is exactly "unlimited supply": a coin used at a smaller amount remains available at a larger amount. Contrast 0/1 knapsack (e.g., Partition Equal Subset Sum), which iterates capacity backward precisely to prevent this - there, dp[c - w] must reflect the state before the current item, so the item is used once. The single line - loop direction - flips the semantics: forward = reuse (unbounded); backward = once (0/1). This is not a stylistic choice; it determines which problem you solve. If you accidentally iterated Coin Change backward, you would forbid coin reuse and solve a different problem (each coin usable once) - wrong for "infinite supply." Conversely, a forward loop in a 0/1 problem wrongly allows reuse. Understanding why (the forward loop lets dp[a-c] already include the current coin) lets you confidently choose the direction based on whether items repeat. Coin Change is the canonical place to internalize the forward loop, just as Partition Equal Subset Sum was for the backward loop. The two problems are mirror images differing only in loop direction, which is the cleanest possible illustration of the 0/1-vs-unbounded distinction.

How does the infinity sentinel handle "impossible" amounts correctly?

Reporting -1 for unreachable amounts (Example 2: amount 3 from only 2-coins) requires careful sentinel handling. We initialize dp[a] = INF for a >= 1 (a value larger than any real coin count) and dp[0] = 0. The transition dp[a] = min(dp[a], dp[a - c] + 1) only improves dp[a] if dp[a - c] is reachable (less than INF); if dp[a - c] is INF (unreachable), then dp[a - c] + 1 is still effectively INF (or larger), so it does not produce a spurious finite value. Thus INF propagates: if no coin combination can build a, every transition into dp[a] comes from an INF predecessor, leaving dp[a] at INF. At the end, dp[amount] == INF (or > amount, the test used) signals "impossible," and we return -1. Two sentinel pitfalls to avoid: (1) Overflow - if INF is Integer.MAX_VALUE, then dp[a - c] + 1 overflows to a negative number, corrupting the min. Using INF = amount + 1 (a value larger than any possible coin count, since you never need more than amount coins of denomination 1) avoids overflow and is a clean sentinel. (2) Spurious reachability - without guarding against INF predecessors (or using a safe sentinel), an unreachable dp[a - c] could wrongly contribute. The INF = amount + 1 choice handles both: amount + 1 never overflows when incremented, and it is unambiguously larger than any real answer (so the final > amount test correctly identifies impossibility). The general lesson for minimization DP with possible "no solution": use a sentinel that is (a) larger than any valid answer and (b) safe under the transition's arithmetic (no overflow when incremented), and ensure it propagates (operations on the sentinel stay "infinite"). This applies to shortest-path DP, minimum-cost DP, and any "minimize, or report impossible" problem. Coin Change is the standard teaching instance: the sentinel marks unreachable amounts, the min transition naturally ignores unreachable predecessors, and the final check distinguishes "minimum found" from "impossible," yielding the correct -1.

Why is greedy (largest coin first) wrong, and why is DP necessary?

A tempting wrong approach is greedy: repeatedly take the largest coin ≤ the remaining amount. For some coin systems (like standard US currency: 1, 5, 10, 25), greedy happens to be optimal - but for arbitrary denominations it is not. Classic counterexample: coins [1, 3, 4], amount 6. Greedy takes 4, then 1, then 1 → three coins (4+1+1). But the optimal is 3 + 3 → two coins. Greedy fails because taking the largest coin can leave an awkward remainder that needs many small coins, whereas a non-greedy choice (two 3s) is better. The reason greedy works for canonical coin systems (and fails generally) is subtle number theory about the denominations; you cannot assume it. So for arbitrary denominations, greedy is incorrect, and DP is necessary - the DP considers all coins at each amount (not just the largest), exploring every way to make the remainder, guaranteeing the true minimum. This is a critical interview point: candidates who reach for greedy on Coin Change get wrong answers on adversarial inputs, while the DP is provably optimal because it exhaustively (but efficiently, via memoization of subproblems) considers every last-coin choice. The deeper lesson: greedy is optimal only when the problem has a specific structure (the greedy-choice property); for general coin change it does not, so use DP. The DP's min over all coins is exactly what greedy lacks - greedy commits to the largest coin irrevocably, while DP keeps all options. When you see "minimum coins / items to reach a target with arbitrary values," reach for the unbounded-knapsack DP, not greedy, unless you can prove the greedy-choice property holds for the specific denominations. This distinction - DP for general optimality, greedy only with proof - recurs across optimization problems (it appeared in the Greedy module's caveats and in Maximum Length of Pair Chain's greedy-vs-DP discussion). Coin Change is the canonical cautionary example where the intuitive greedy is wrong.

How does Coin Change relate to the other unbounded knapsack problems?

Coin Change is the minimize-count archetype of the unbounded knapsack sub-group, and the others are variations on the same forward-loop machine. Coin Change II (next topic) changes the objective from minimize the number of coins to count the number of combinations that make the amount - same items (reusable coins), same forward reuse, but the operator changes from min to + (counting), and the loop order becomes critical (items-outer to count unordered combinations, avoiding double-counting different orderings). Perfect Squares is literally Coin Change with the "coins" being the perfect squares (1, 4, 9, 16, ...) and the target being n - minimize the count of squares summing to n, the identical min over items of dp[remainder] + 1 transition with a different (reusable) item set. Minimum Cost For Tickets is a cost-minimizing unbounded-ish variant where "items" are travel passes of different durations and the structure is over days, minimizing total cost. All share the unbounded structure - reach a target using reusable items, forward loop - and differ in objective (minimize count / count ways / minimize cost) and item set (coins / squares / passes). Coin Change establishes the minimize-count operator (min, +1 per item) and the impossibility sentinel; recognizing that Perfect Squares is "Coin Change with square coins" or that a problem is "Coin Change with these items" is the transferable pattern-spotting. The sub-group thereby teaches that once you recognize "reach a target with reusable items," you instantiate the unbounded knapsack with the right operator (min for fewest, + for count) and item set, and choose the loop order (matters only for counting). Coin Change is the foundation: the most common interview instance, the minimize-count operator, the forward-loop reuse, and the sentinel-based impossibility handling that the rest of the sub-group builds upon.

What about edge cases?

amount = 0: Zero coins make amount 0; dp[0] = 0, return 0.
Impossible amount (Example 2): No coin combination reaches it; INF propagates, return -1.
Single coin dividing the amount: e.g., coins = [5], amount = 10 → 2 coins; the DP finds it.
Coin larger than amount: Skipped by the c <= a check; never used.
Large amount (up to 10^4) with few coins: O(amount · #coins) ≈ 1.2×10⁵ operations - efficient.

Common Interview Pitfalls

Using greedy (largest coin first). Incorrect for arbitrary denominations (e.g., [1,3,4], amount 6: greedy gives 3 coins, optimal is 2); use DP.
Sentinel overflow. Integer.MAX_VALUE + 1 overflows; use INF = amount + 1 and the > amount test.
Backward loop. Coins are reusable; iterate amount forward. A backward loop solves the wrong (0/1) problem.
Forgetting the impossible case. Check whether dp[amount] remains the sentinel and return -1.

Why This Topic Matters

Coin Change is the canonical minimize-count unbounded knapsack: dp[a] = min over coins c of dp[a - c] + 1, with the forward capacity loop allowing each coin to be reused (because dp[a - c] may already include coin c). It teaches the forward-loop reuse semantics (mirror image of 0/1's backward loop), the infinity-sentinel handling of unreachable amounts (using amount + 1 to avoid overflow and propagate "impossible" to a correct -1), and the crucial lesson that greedy is wrong for arbitrary denominations - DP is necessary because it considers every last-coin choice. It is the foundation the rest of the unbounded sub-group builds on.

The next topic, Coin Change II, keeps the same reusable coins and target but changes the objective from minimize the number of coins to count the number of distinct combinations that sum to the amount. The DP defines dp[a] = the number of combinations making amount a, with the transition accumulating over coins - but the loop order becomes essential: iterating coins on the outer loop and amount on the inner loop counts unordered combinations (each coin's contribution is layered once across all amounts, so 1+2 and 2+1 are the same combination counted once), whereas the reverse order would count ordered permutations. It introduces the counting unbounded knapsack and, critically, the loop-order distinction that separates counting combinations from counting permutations - one of the most subtle and important points in all of dynamic programming.

Back to DSA Mastery - Interview Prep, End to End