Approach Summary
dp[i] = min coins to make amount i. For each amount, try all coins: dp[i] = min(dp[i], dp[i - coin] + 1).
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Top-Down Recursion with Memoization | O(amount * n) | O(amount) recursion stack + memo | Recursively search the minimum coins needed for remainder with a memo table to prune repeated branches. |
| 2 Approach 2: Bottom-Up 1D Dynamic Programming (Optimal) | O(amount * n) | O(amount) | Iteratively build fewest coins needed from 1 up to target amount using dp[i] = min(dp[i], dp[i - coin] + 1). |
Step 1: Baseline
Approach 1: Top-Down Recursion with Memoization
Time: O(amount * n)
Space: O(amount) recursion stack + memo
Define solve(rem) as the minimum coins needed to make amount rem. If rem == 0 return 0; if rem < 0 return -1. For each coin, recursively compute solve(rem - coin). If valid, record min. Cache the result in a memoization map or array to eliminate redundant sub-tree calculations.
Approach 1: Top-Down Recursion with Memoization Implementation
Approach 1: Top-Down Recursion with Memoization
class Solution {
private int solve(int[] coins, int rem, int[] memo) {
if (rem == 0) return 0;
if (rem < 0) return -1;
if (memo[rem] != 0) return memo[rem];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int res = solve(coins, rem - coin, memo);
if (res >= 0 && res < minCoins) {
minCoins = res + 1;
}
}
memo[rem] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[rem];
}
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
return solve(coins, amount, new int[amount + 1]);
}
}class Solution {
public:
int solve(vector<int>& coins, int rem, vector<int>& memo) {
if (rem == 0) return 0;
if (rem < 0) return -1;
if (memo[rem] != 0) return memo[rem];
int minCoins = INT_MAX;
for (int coin : coins) {
int res = solve(coins, rem - coin, memo);
if (res >= 0 && res < minCoins) {
minCoins = res + 1;
}
}
memo[rem] = (minCoins == INT_MAX) ? -1 : minCoins;
return memo[rem];
}
int coinChange(vector<int>& coins, int amount) {
if (amount < 1) return 0;
vector<int> memo(amount + 1, 0);
return solve(coins, amount, memo);
}
};class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
memo = {}
def solve(rem):
if rem == 0:
return 0
if rem < 0:
return -1
if rem in memo:
return memo[rem]
min_coins = float('inf')
for coin in coins:
res = solve(rem - coin)
if res >= 0 and res < min_coins:
min_coins = res + 1
memo[rem] = min_coins if min_coins != float('inf') else -1
return memo[rem]
return solve(amount)function coinChange(coins, amount) {
const memo = new Map();
function solve(rem) {
if (rem === 0) return 0;
if (rem < 0) return -1;
if (memo.has(rem)) return memo.get(rem);
let minCoins = Infinity;
for (const coin of coins) {
const res = solve(rem - coin);
if (res >= 0 && res < minCoins) {
minCoins = res + 1;
}
}
const ans = minCoins === Infinity ? -1 : minCoins;
memo.set(rem, ans);
return ans;
}
return solve(amount);
} Step 2: Most Optimized
Approach 2: Bottom-Up 1D Dynamic Programming (Optimal)
Time: O(amount * n)
Space: O(amount)
Create an array dp of length amount + 1 initialized with sentinel infinity amount + 1. Base case dp[0] = 0. Iterate from 1 to amount, testing every coin. If coin <= i, relax dp[i] = min(dp[i], dp[i - coin] + 1). This bottom-up approach eliminates recursion stack overhead and achieves peak cache locality.
Approach 2: Bottom-Up 1D Dynamic Programming (Optimal) Implementation
Approach 2: Bottom-Up 1D Dynamic Programming (Optimal)
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] <= amount else -1function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}Edge Cases to Watch
- amount = 0 (0 coins required; returns 0)
- No combination can make amount (e.g. coins = [2], amount = 3; returns -1)
- Coins larger than amount (e.g. coins = [5], amount = 3; skipped during loop)
- Coin denominations not sorted (unbounded DP handles any order correctly)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Minimum coins to make amount
- Unbounded knapsack
Complexity Analysis
Time Complexity
O(amount × n)
Space Complexity
O(amount)
Tags
Array DP BFS
Frequently Asked Questions
What is the optimal time and space complexity for Coin Change?
The optimal solution for Coin Change achieves O(amount × n) runtime complexity and requires O(amount) auxiliary space. Time complexity is O(amount * n) where n is the number of coins, as we evaluate every coin for each sub-amount from 1 to amount. Space complexity is O(amount) for the 1D DP table.
How do I identify that Coin Change requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Minimum coins to make amount; Unbounded knapsack. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Coin Change?
Essential edge cases to verify include: amount = 0 (0 coins required; returns 0); No combination can make amount (e.g. coins = [2], amount = 3; returns -1); Coins larger than amount (e.g. coins = [5], amount = 3; skipped during loop); Coin denominations not sorted (unbounded DP handles any order correctly). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Coin Change?
Coin Change is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Microsoft, Goldman Sachs.