Skip to content

Volume ITechnology

4.23.8 — Coin Change ​

LeetCode 322 · Medium · ★ Blind 75

The problem ​

Given coin denominations and an amount, return the fewest coins that make the amount, or -1 if it cannot be made. You have unlimited coins of each type.

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

Amount up to 10,000.

Restating the Problem: You are a cashier tasked with returning a specific amount of change, but you want to give the customer the fewest physical coins possible. You have a bottomless drawer of each coin denomination provided.

Constraints to Note:

  • The amount can be up to 10^4.
  • You can have up to 12 different coin denominations.
  • A coin's value can be up to 2^{31} - 1.
  • Because of the amount limit, an O(Amount \times Coins) algorithm will take at most 120,000 operations, which is incredibly fast.

The brute force, and where it wastes work ​

The brute force method is to explore every possible coin choice. At each step, if we need to make amount A, we try subtracting each coin denomination C. Then we recursively find the fewest coins to make A - C. Since we can reuse coins, each recursive step branches into K paths (where K is the number of coin types). The depth of the recursion can be up to Amount (if we just use 1-cent coins). This yields a time complexity of O(K^{Amount}). For amount=11 and 3 coins, that's 3^{11} \approx 177,000. For amount=10,000, it's literally impossible to compute in a human lifetime. We must memoize or use DP.

Why greedy fails ​

This is the standard example for the DP-versus-greedy question from 4.22, so have the counterexample ready.

Greedy rule: always take the largest coin that fits.

Counterexample: coins = [1, 3, 4], amount = 6. Greedy takes 4, then 1, then 1 — three coins. The right answer is 3 + 3 — two coins.

Real currencies are deliberately designed so that greedy works, which is exactly why the intuition is so strong and so wrong. When the denominations are arbitrary, greedy is not safe, and one counterexample settles it.

The pattern ​

Let dp[a] be the fewest coins making amount a.

To make amount a, the last coin you used was some coin c. Before that you had made a − c, using dp[a - c] coins. So:

dp[a] = 1 + \min_{c \,\in\, \text{coins},\ c \le a} dp[a - c]

Read aloud: the cheapest way to make a is one coin, plus the cheapest way to make whatever was left after that coin. Try every coin as the last one and keep the best.

dp[0] = 0 — making zero needs no coins. That is the base case and everything builds from it.

The solution ​

python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1                     # (1) bigger than any real answer
        dp = [INF] * (amount + 1)  # (2)
        dp[0] = 0  # (3)

        for a in range(1, amount + 1):  # (4)
            for c in coins:  # (5)
                if c <= a:  # (6)
                    dp[a] = min(dp[a], 1 + dp[a - c])  # (7)

        return dp[amount] if dp[amount] != INF else -1  # (8)
ts
function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;  // (1)
  const dp = new Array(amount + 1).fill(INF);  // (2)
  dp[0] = 0;  // (3)

  for (let a = 1; a <= amount; a++) {  // (4)
    for (const c of coins) {  // (5)
      if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);  // (6)
    }
  }

  return dp[amount] === INF ? -1 : dp[amount];  // (8)
}

Line by line ​

Here dp[a] means "the fewest coins that add up to exactly a".

(1) A stand-in for "impossible". No amount needs more than amount coins, even using only coins of 1. So amount + 1 can never be a real answer, and it is safe to use as "cannot be made". It is used instead of infinity so that 1 + INF stays an ordinary number.

(2) Every amount starts as impossible.

(3) An amount of 0 needs 0 coins. Every other answer is built on this one.

(4) Work out every amount from 1 up to the target. Smaller amounts are always finished first, because each answer is built from smaller ones.

(5) Try each coin as the last coin used.

(6) The coin must not be bigger than the amount.

(7) Using coin c last costs one coin plus the fewest coins for what is left, a − c. Keep the smallest result over all coins. In TypeScript the same step is on line (6), written on one line.

(8) If the target is still "impossible", return −1.

INF = amount + 1 rather than infinity. The most coins any reachable amount could need is amount (all 1s), so amount + 1 is unreachable and marks "impossible" without needing floats. It also keeps 1 + dp[...] safe from overflow concerns in typed languages.

The loop order. dp[a] reads dp[a - c], which is always smaller, so the outer loop counts upwards and every cell it needs is already filled.

Coins may be reused freely, and the code allows that automatically: dp[a - c] may itself have used coin c. Compare 4.23.12 Partition Equal Subset Sum, where each item is used once, and the loop must run downwards to prevent reuse. That loop direction is the entire difference between the two problems. It is the mistake named in 4.22.

Trace ​

coins = [1, 2, 5], amount = 6

abest optiondp[a]
11 + dp[0]1
21 + dp[0] via coin 21
31 + dp[1] via coin 22
41 + dp[2] via coin 22
51 + dp[0] via coin 51
61 + dp[5] via coin 12

Two coins for 6: 5 + 1 ✓.

Edge cases ​

  • amount = 0. No coins are needed. dp[0] = 0 is returned.
  • No combination works, like coins [2] and amount 3. dp[3] stays impossible, so −1.
  • A single coin of 1. Every amount a needs exactly a coins.

The top-down version ​

python
from functools import lru_cache

def coinChange(self, coins, amount):
    @lru_cache(None)
    def fewest(a: int) -> float:
        if a == 0: return 0
        if a < 0: return float('inf')
        return min((1 + fewest(a - c) for c in coins), default=float('inf'))

    result = fewest(amount)
    return -1 if result == float('inf') else result

Easier to derive, because it is just the recurrence written down. It costs stack depth and hash lookups, and it computes only the amounts actually reachable — which is a genuine advantage when the coins are large and most amounts are unreachable.

Derive with this, ship the table.

Complexity ​

O(\text{amount} \times \text{number of coins}) time, O(\text{amount}) space.

Time Complexity Derivation: We have an outer loop running from 1 to amount (which is O(\text{amount}) iterations). Inside that, we loop through all C coin denominations (which is O(\text{coins}) iterations). The operation inside the inner loop is an O(1) constant-time lookup and addition. Multiplying these gives O(\text{amount} \times \text{coins}).

Space Complexity Derivation: We create a 1D array dp of size amount + 1 to store the fewest coins for every amount up to the target. This directly takes O(\text{amount}) memory. We don't use any other data structures.

This is pseudo-polynomial. The runtime is polynomial in the value of the amount, not in the number of digits used to write it. Adding one more digit to the amount multiplies the work by ten. Coin Change is a cousin of the knapsack problem for exactly this reason, and 4.29 explains why that matters.

Where this goes next ​

  • Coin Change II — count the number of combinations rather than the fewest coins. The loop order flips: coins outside, amounts inside, or you count permutations by accident. That is 4.24.4 and it is one of the most instructive loop-order lessons in the book.
  • Combination Sum IV — counts permutations, so the loops go the other way round. Compare the two and the difference becomes obvious.
  • Perfect Squares — Coin Change where the coins are 1, 4, 9, 16 and so on.
  • Minimum Cost For Tickets — the same shape with three "coins" of different durations.

What the interviewer will push on ​

"Why not greedy?" [1, 3, 4] and amount 6. Have it ready before they ask.

"What does dp[a] mean?" The fewest coins making exactly a.

"Why dp[0] = 0?" Zero needs no coins, and every other value is built from it.

"How do you mark impossible?" A sentinel larger than any real answer, then convert to -1 at the end.

"Why does the loop go upwards, and when would it go down?" Upwards allows reuse. Downwards prevents it, which is what 0/1 knapsack needs.

"What is the complexity, and is that polynomial?" O(\text{amount} \times \text{coins}), and it is pseudo-polynomial — polynomial in the value, not in the input size.

"How would you return the actual coins?" Store, for each amount, which coin gave the best answer, then walk backwards from amount. Reconstruction needs the table, which is the one thing the O(1)-space tricks give up.

One thing to volunteer: open with the greedy counterexample. It settles the technique choice in ten seconds and shows you tested your first instinct instead of trusting it.

Next: 4.23.9 Maximum Product Subarray — where you have to carry two values because a negative can turn the worst into the best.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet