Master Coin Change Problem (Leetcode 322) with This Easy Tutorial


❓ The Problem
You’re given an array of coin denominations (e.g.
[1, 2, 5]
)
and a target amount (e.g.11
).
Return the minimum number of coins needed to make up that amount.
If it's not possible, return-1
.
🎯 What You’re Really Being Asked
Find the shortest path to a number, using only steps defined by the coins.
For example:
coins = [1, 2, 5]
amount = 11
You could make 11 in a ton of ways:
1+1+1+...+1
(11 coins)5+5+1
(3 coins)2+2+2+5
(4 coins)
But you want the way that uses the fewest total coins.
💣 Why This Problem Is Confusing
Most people throw this at you:
minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin])
And you’re left going:
Where is this coming from?
Why is
minCoins[i]
being compared to itself?What the hell is this “bottom-up” thing and why does it work?
This blog answers all of that.
✅ Step-by-Step Plan That Actually Makes Sense
🧱 Step 1: Define the Meaning of DP
We create:
minCoins[i] = the minimum number of coins needed to make amount i
We’re going to fill this from 0
up to amount
.
🚨 Base Case:
minCoins[0] = 0
Why?
Because it takes 0 coins to make amount 0.
(You don’t need anything.)
🧱 Initial Setup:
We assume all other amounts are impossible by default.
So we set them to “infinity” (amount + 1
is safe):
let minCoins = new Array(amount + 1).fill(amount + 1);
minCoins[0] = 0;
This says:
“I don’t yet know how to make amount 1, 2, ...,
amount
—
but I’ll try to find better answers as I go.”
🧠 Step 2: Core Logic — Build Up the Answer
Now the key idea:
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (i - coin >= 0) {
minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin]);
}
}
}
Let's break it line by line:
🔁 Outer Loop: for (i = 1 to amount)
“Let me solve for amount = 1, 2, 3, ...,
amount
one by one.”
We’re building answers from the bottom up.
🔁 Inner Loop: for (coin of coins)
“For this current amount, let me try every coin I have.
Each one could be the last coin used to make this amount.”
🔥 The Real Brain of the Algorithm:
minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin]);
🚨 Read this in real words:
“If I use coin
c
now, then I only need to figure out how to buildamount - c
.
That’sminCoins[i - coin]
.
So I take that answer, add 1 (for the current coin), and see if it's better than what I had before.”
📈 Example: coins = [1, 3, 4], amount = 6
Let’s walk through how we build minCoins[6]
.
Start with:
minCoins = [0, ∞, ∞, ∞, ∞, ∞, ∞]
0 1 2 3 4 5 6
i = 1
Try 1:
1 + minCoins[0] = 1 + 0 = 1
✅Others invalid
minCoins = [0, 1, ∞, ∞, ∞, ∞, ∞]
i = 2
- Try 1:
1 + minCoins[1] = 1 + 1 = 2
minCoins = [0, 1, 2, ∞, ∞, ∞, ∞]
i = 3
Try 1:
1 + minCoins[2] = 1 + 2 = 3
Try 3:
1 + minCoins[0] = 1 + 0 = 1
✅
minCoins = [0, 1, 2, 1, ∞, ∞, ∞]
i = 4
Try 1:
1 + minCoins[3] = 1 + 1 = 2
Try 3:
1 + minCoins[1] = 1 + 1 = 2
Try 4:
1 + minCoins[0] = 1 + 0 = 1
✅
minCoins = [0, 1, 2, 1, 1, ∞, ∞]
i = 5
Try 1:
1 + minCoins[4] = 1 + 1 = 2
✅Try 3:
1 + minCoins[2] = 1 + 2 = 3
Try 4:
1 + minCoins[1] = 1 + 1 = 2
minCoins = [0, 1, 2, 1, 1, 2, ∞]
i = 6
Try 1:
1 + minCoins[5] = 1 + 2 = 3
Try 3:
1 + minCoins[3] = 1 + 1 = 2
✅Try 4:
1 + minCoins[2] = 1 + 2 = 3
minCoins = [0, 1, 2, 1, 1, 2, 2]
✅ Final Answer:
minCoins[6] = 2
You can form 6 using: 3 + 3
or 1 + 1 + 4
→ both use 2 coins.
🔁 Forward vs Reverse Loop
You don’t need reverse loop in this problem.
Why?
Because every time you do:
minCoins[i] = 1 + minCoins[i - coin]
,
you’re only reading past values (from smaller i’s)
✅ Those values have already been finalized in earlier steps
✅ So forward loop works just fine
You’d use reverse loop only when:
You must not reuse the same item in the same iteration
Like in 0/1 Knapsack (where each item can be used at most once)
Not here. You can reuse coins as many times as you like.
🔚 Return Value
Finally:
return minCoins[amount] !== amount + 1 ? minCoins[amount] : -1;
If it’s still the "infinity" value → No solution found → return -1
Otherwise, return the best answer.
🧠 TL;DR Mental Model
For each amount
i
Try every coin
c
Think:
“If I use
c
now, how many coins did it take to formi - c
?”
Add1
for the current coin
Keep the best result
That’s it. That’s the chain reaction you wanted to visualize.
💬 Final Thoughts
Coin Change is a classic — not because it's hard,
but because it's so easy to explain badly.
If someone had just said:
“Think of coins as steps, and amount as the top of a staircase.
You’re trying to reach the top with as few steps as possible,
trying every footstep that gets you closer,
and always remembering what the best path to each stair looked like.”
You’d have gotten it on Day 1..
Subscribe to my newsletter
Read articles from Kshitij Sharma directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Kshitij Sharma
Kshitij Sharma
A Software Engineer who writes about what he learns in his free time