Coin Change
A medium Dynamic Programming problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Dynamic Programming
- Sheets
- 3
- Core for
- 9 roles
- Platform
- LeetCode
The problem
You are given an integer array of coin denominations and a total amount. Find the fewest number of coins needed to make up that amount. If it is impossible, return -1.
Example 1
- Input
- coins = [1,2,5], amount = 11
- Output
- 3
- Why
- 11 = 5 + 5 + 1, using 3 coins.
Example 2
- Input
- coins = [2], amount = 3
- Output
- -1
- Why
- It is impossible to make 3 with only coins of denomination 2.
Example 3
- Input
- coins = [1], amount = 0
- Output
- 0
- Why
- No coins needed when the amount is already 0.
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
How to think about it
Updated 2026-09-09Every coin value reduces the remaining target by a fixed step, making the fewest coins to form any total depend purely on the fewest coins needed for smaller totals. Instead of asking which branch to take, build up answers by trying every coin from the bottom up: the optimal answer for any sum is one plus the cheapest predecessor.
Approaches, worst first
Recursive search
time O(k^amount) · space O(amount)
Try subtracting each coin denomination from the target and recurse on the remainder. Without caching it recalculates identical sub-amounts millions of times, generating an enormous tree that quickly exceeds the execution limit.
Memoized search
time O(amount * k) · space O(amount)
Run top-down recursion while storing the minimum coins needed for each remaining amount in a table. It trims duplicate work, but the recursion stack incurs overhead for deep targets.
Iterative bottom-up tableWrite this one
time O(amount * k) · space O(amount)
Initialize an array of size amount + 1 filled with infinity, set dp[0] = 0, and iterate from 1 to amount. For each amount, check every coin: dp[i] = min(dp[i], dp[i - c] + 1). It runs entirely in simple loops without call-frame overhead.
Where people lose marks · 4
- Initializing the array with 0 or -1 instead of an unreachable sentinel like amount + 1. If 0 is used as empty, min comparisons treat unreachable states as free.
- Target amount of 0 requires exactly 0 coins. Returning -1 or failing to handle 0 breaks the base case before any coin is examined.
- Coin values can exceed 2^31 - 1. When amount is small, accessing dp[i - coin] directly without checking if coin <= i leads to negative indexing or out-of-bounds reads.
- Assuming the greedy strategy of picking the largest coin first works. For coins [1, 6, 7] and amount 12, greedy takes 7 + 1 + 1 + 1 + 1 + 1 (6 coins) instead of 6 + 6 (2 coins).
Full solution
Iterative bottom-up table (the notes' recommended approach): dp[i] holds the fewest coins for amount i, filled with an unreachable sentinel (amount + 1) so min() never mistakes 'unreachable' for 'free'.
Python
def coin_change(coins: list[int], amount: int) -> int:
unreachable = amount + 1
dp = [unreachable] * (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] != unreachable else -1
JavaScript
function coinChange(coins, amount) {
const unreachable = amount + 1;
const dp = new Array(amount + 1).fill(unreachable);
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] === unreachable ? -1 : dp[amount];
}
The theory behind it
Dynamic Programming — the ground this problem stands on. All Dynamic Programming problems
What Dynamic Programming is
Dynamic programming is a method for solving a complex problem by breaking it into overlapping subproblems, solving each subproblem only once, and remembering the answers in a lookup table. Instead of recalculating identical questions over and over, future steps look up previous answers directly. By assembling these saved pieces from the bottom up or storing them during recursion, a task that would take billions of steps finishes in a fraction of a second.
When to reach for it
Reach for dynamic programming when questions ask for the maximum profit, minimum cost, total number of distinct ways to achieve a goal, or whether a target can be formed. Signals include overlapping choices where making a choice now affects what choices remain later, but greedy picking fails to find the true global optimum. If drawing a recursive decision tree reveals the same subproblem states repeating across branches, dynamic programming is needed.
How the pattern works
Identify the state variables that uniquely describe a subproblem, such as an array index and remaining capacity. Write the base cases first, representing states whose answers are known without calculation. Next, write the recurrence relation that expresses the current state using previously solved states, taking the minimum, maximum, or sum among your options. Build the solution either top-down by caching recursive returns in a memo table, or bottom-up by filling an array in topological dependency order. When each state depends only on the previous row, compress storage down to a single array.
What each operation costs
| Operation | Time |
|---|---|
| fill dynamic programming table of n states | O(n) |
| solve two-dimensional grid of m by n states | O(m * n) |
| space-optimized state transition keeping one row | O(n) |
What usually goes wrong with Dynamic Programming
- Filling a bottom-up table in an order where the current cell needs values that have not been computed yet, reading uninitialized zeros.
- Failing to initialize base cases properly, such as filling a minimization table with zeros instead of infinity, which traps the answer at zero.
- Overwriting values in a 1D space-optimized knapsack array by scanning in the wrong direction, allowing the same item to be chosen multiple times.
Which roles need this problem
Dynamic Programming is a core topic for these 9 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 5 more roles, including Game Developer, Cryptography Engineer, Performance Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Dynamic Programming problems
Problem set and role mapping as of .