Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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.
Input:
- An array of integers
coinsrepresenting coin denominations - An integer
amountrepresenting the target amount
Output:
- The minimum number of coins needed to make the amount, or -1 if impossible
Constraints:
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ - 1
- 0 ≤ amount ≤ 10⁴
Examples:
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1 (3 coins)
Example 2:
Input: coins = [2], amount = 3
Output: -1
Explanation: Cannot make amount 3 with only coin of denomination 2
Example 3:
Input: coins = [1], amount = 0
Output: 0
Explanation: No coins needed to make amount 0
Example 4:
Input: coins = [1, 3, 4], amount = 6
Output: 2
Explanation: 6 = 3 + 3 (2 coins)
Solutions
Approach 1: Recursive Solution with Memoization (Top-Down DP)
Use recursion with memoization to explore all possible combinations and find the minimum.
Algorithm:
- For each amount, try using each coin denomination
- Recursively find the minimum coins for remaining amount
- Use memoization to avoid recomputing the same subproblems
Python:
def coinChange_recursive(coins, amount):
"""
Recursive solution with memoization (top-down DP)
Time: O(amount * len(coins)) - each subproblem computed once
Space: O(amount) - memoization table + recursion stack
"""
memo = {}
def dfs(remaining):
# Base cases
if remaining == 0:
return 0
if remaining < 0:
return -1
if remaining in memo:
return memo[remaining]
min_coins = float('inf')
# Try each coin
for coin in coins:
result = dfs(remaining - coin)
if result != -1: # Valid solution found
min_coins = min(min_coins, result + 1)
# Store result (-1 if no valid solution)
memo[remaining] = -1 if min_coins == float('inf') else min_coins
return memo[remaining]
return dfs(amount)
def coinChange_memo_optimized(coins, amount):
"""
Optimized memoization with early termination
Time: O(amount * len(coins))
Space: O(amount)
"""
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
return min(dp(remaining - coin) + 1 for coin in coins)
result = dp(amount)
return result if result != float('inf') else -1
# Example usage
print(coinChange_recursive([1, 2, 5], 11)) # Output: 3
Java:
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
class Solution {
private Map<Integer, Integer> memo = new HashMap<>();
/**
* Recursive solution with memoization
* Time: O(amount * coins.length)
* Space: O(amount)
*/
public int coinChange(int[] coins, int amount) {
return dfs(coins, amount);
}
private int dfs(int[] coins, int remaining) {
// Base cases
if (remaining == 0) {
return 0;
}
if (remaining < 0) {
return -1;
}
if (memo.containsKey(remaining)) {
return memo.get(remaining);
}
int minCoins = Integer.MAX_VALUE;
// Try each coin
for (int coin : coins) {
int result = dfs(coins, remaining - coin);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
// Store result
int finalResult = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
memo.put(remaining, finalResult);
return finalResult;
}
/**
* Alternative implementation with array memoization
* Time: O(amount * coins.length)
* Space: O(amount)
*/
public int coinChangeArrayMemo(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2); // -2 means uncomputed, -1 means impossible
return dfsArray(coins, amount, memo);
}
private int dfsArray(int[] coins, int remaining, int[] memo) {
if (remaining == 0) return 0;
if (remaining < 0) return -1;
if (memo[remaining] != -2) return memo[remaining];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = dfsArray(coins, remaining - coin, memo);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
memo[remaining] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[remaining];
}
}
Go:
// coinChangeRecursive - Recursive solution with memoization
// Time: O(amount * len(coins))
// Space: O(amount)
func coinChangeRecursive(coins []int, amount int) int {
memo := make(map[int]int)
var dfs func(remaining int) int
dfs = func(remaining int) int {
// Base cases
if remaining == 0 {
return 0
}
if remaining < 0 {
return -1
}
if val, exists := memo[remaining]; exists {
return val
}
minCoins := math.MaxInt32
// Try each coin
for _, coin := range coins {
result := dfs(remaining - coin)
if result != -1 {
minCoins = min(minCoins, result+1)
}
}
// Store result
if minCoins == math.MaxInt32 {
memo[remaining] = -1
} else {
memo[remaining] = minCoins
}
return memo[remaining]
}
return dfs(amount)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
JavaScript:
/**
* Recursive solution with memoization
* Time: O(amount * coins.length)
* Space: O(amount)
*/
function coinChangeRecursive(coins, amount) {
const memo = new Map();
function dfs(remaining) {
// Base cases
if (remaining === 0) return 0;
if (remaining < 0) return -1;
if (memo.has(remaining)) return memo.get(remaining);
let minCoins = Infinity;
// Try each coin
for (const coin of coins) {
const result = dfs(remaining - coin);
if (result !== -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
// Store result
const finalResult = minCoins === Infinity ? -1 : minCoins;
memo.set(remaining, finalResult);
return finalResult;
}
return dfs(amount);
}
/**
* Using object for memoization
* Time: O(amount * coins.length)
* Space: O(amount)
*/
function coinChangeMemoObject(coins, amount) {
const memo = {};
function dp(remaining) {
if (remaining === 0) return 0;
if (remaining < 0) return Infinity;
if (remaining in memo) return memo[remaining];
const result = Math.min(...coins.map(coin => dp(remaining - coin) + 1));
memo[remaining] = result;
return result;
}
const result = dp(amount);
return result === Infinity ? -1 : result;
}
C#:
using System;
using System.Collections.Generic;
public class Solution {
private Dictionary<int, int> memo = new Dictionary<int, int>();
/// <summary>
/// Recursive solution with memoization
/// Time: O(amount * coins.Length)
/// Space: O(amount)
/// </summary>
public int CoinChange(int[] coins, int amount) {
return Dfs(coins, amount);
}
private int Dfs(int[] coins, int remaining) {
// Base cases
if (remaining == 0) return 0;
if (remaining < 0) return -1;
if (memo.ContainsKey(remaining)) return memo[remaining];
int minCoins = int.MaxValue;
// Try each coin
foreach (int coin in coins) {
int result = Dfs(coins, remaining - coin);
if (result != -1) {
minCoins = Math.Min(minCoins, result + 1);
}
}
// Store result
int finalResult = minCoins == int.MaxValue ? -1 : minCoins;
memo[remaining] = finalResult;
return finalResult;
}
}
Approach 2: Bottom-Up Dynamic Programming (Tabulation)
Build the solution iteratively from amount 0 to target amount.
Algorithm:
- Create a DP array where dp[i] represents minimum coins for amount i
- Initialize dp[0] = 0, all others to infinity
- For each amount, try all coins and take the minimum
Python:
def coinChange_tabulation(coins, amount):
"""
Bottom-up DP solution (tabulation)
Time: O(amount * len(coins)) - nested loops
Space: O(amount) - DP array
"""
# dp[i] = minimum coins needed for amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins needed for amount 0
# For each amount from 1 to target
for curr_amount in range(1, amount + 1):
# Try each coin
for coin in coins:
if coin <= curr_amount:
dp[curr_amount] = min(dp[curr_amount], dp[curr_amount - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coinChange_tabulation_optimized(coins, amount):
"""
Optimized tabulation with early termination
Time: O(amount * len(coins))
Space: O(amount)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for curr_amount in range(1, amount + 1):
for coin in coins:
if coin <= curr_amount and dp[curr_amount - coin] != float('inf'):
dp[curr_amount] = min(dp[curr_amount], dp[curr_amount - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Example usage
print(coinChange_tabulation([1, 2, 5], 11)) # Output: 3
Java:
import java.util.Arrays;
class Solution {
/**
* Bottom-up DP solution
* Time: O(amount * coins.length)
* Space: O(amount)
*/
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0; // Base case
for (int currAmount = 1; currAmount <= amount; currAmount++) {
for (int coin : coins) {
if (coin <= currAmount && dp[currAmount - coin] != Integer.MAX_VALUE) {
dp[currAmount] = Math.min(dp[currAmount], dp[currAmount - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
/**
* Alternative implementation with cleaner logic
* Time: O(amount * coins.length)
* Space: O(amount)
*/
public int coinChangeAlternative(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // Use amount + 1 as "infinity"
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
Go:
// coinChangeTabulation - Bottom-up DP solution
// Time: O(amount * len(coins))
// Space: O(amount)
func coinChangeTabulation(coins []int, amount int) int {
dp := make([]int, amount+1)
// Initialize with max value (infinity)
for i := range dp {
dp[i] = amount + 1
}
dp[0] = 0 // Base case
for currAmount := 1; currAmount <= amount; currAmount++ {
for _, coin := range coins {
if coin <= currAmount {
dp[currAmount] = min(dp[currAmount], dp[currAmount-coin]+1)
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
JavaScript:
/**
* Bottom-up DP solution
* Time: O(amount * coins.length)
* Space: O(amount)
*/
function coinChangeTabulation(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // Base case
for (let currAmount = 1; currAmount <= amount; currAmount++) {
for (const coin of coins) {
if (coin <= currAmount) {
dp[currAmount] = Math.min(dp[currAmount], dp[currAmount - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
/**
* Using amount + 1 as infinity for cleaner code
* Time: O(amount * coins.length)
* Space: O(amount)
*/
function coinChangeTabulationClean(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 (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
C#:
using System;
public class Solution {
/// <summary>
/// Bottom-up DP solution
/// Time: O(amount * coins.Length)
/// Space: O(amount)
/// </summary>
public int CoinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0; // Base case
for (int currAmount = 1; currAmount <= amount; currAmount++) {
foreach (int coin in coins) {
if (coin <= currAmount && dp[currAmount - coin] != int.MaxValue) {
dp[currAmount] = Math.Min(dp[currAmount], dp[currAmount - coin] + 1);
}
}
}
return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
/// <summary>
/// Using amount + 1 as infinity
/// Time: O(amount * coins.Length)
/// Space: O(amount)
/// </summary>
public int CoinChangeClean(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Array.Fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
foreach (int coin in coins) {
if (i >= coin) {
dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
Approach 3: BFS Solution
Use BFS to find the shortest path (minimum coins) to reach the target amount.
Python:
def coinChange_bfs(coins, amount):
"""
BFS solution - finds shortest path to target
Time: O(amount * len(coins)) - each amount visited once
Space: O(amount) - queue and visited set
"""
if amount == 0:
return 0
from collections import deque
queue = deque([(0, 0)]) # (current_amount, num_coins)
visited = set([0])
while queue:
curr_amount, num_coins = queue.popleft()
# Try each coin
for coin in coins:
next_amount = curr_amount + coin
if next_amount == amount:
return num_coins + 1
if next_amount < amount and next_amount not in visited:
visited.add(next_amount)
queue.append((next_amount, num_coins + 1))
return -1
# Example usage
print(coinChange_bfs([1, 2, 5], 11)) # Output: 3
Java:
import java.util.*;
class Solution {
/**
* BFS solution
* Time: O(amount * coins.length)
* Space: O(amount)
*/
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(0);
visited.add(0);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
int currAmount = queue.poll();
for (int coin : coins) {
int nextAmount = currAmount + coin;
if (nextAmount == amount) {
return level;
}
if (nextAmount < amount && !visited.contains(nextAmount)) {
visited.add(nextAmount);
queue.offer(nextAmount);
}
}
}
}
return -1;
}
}
Key Insights
- Unbounded Knapsack Pattern: Each coin can be used unlimited times
- Optimal Substructure: Minimum coins for amount X = min(coins for X-coin) + 1
- Overlapping Subproblems: Same amounts computed multiple times in naive recursion
- Greedy Doesn’t Work: Largest coin first doesn’t always give optimal solution
- BFS as Alternative: Shortest path perspective using level-order traversal
Edge Cases
- amount = 0: Return 0 (no coins needed)
- Impossible cases: When no combination can make the amount
- Single coin solutions: When amount is divisible by one coin
- Large denominations: Coins larger than the target amount
- Duplicate coins: Array might contain duplicate values
Test Cases
def test_coin_change():
test_cases = [
([1, 2, 5], 11, 3),
([2], 3, -1),
([1], 0, 0),
([1, 3, 4], 6, 2),
([1, 2, 5], 7, 2),
([186, 419, 83, 408], 6249, 20)
]
for coins, amount, expected in test_cases:
result = coinChange_tabulation(coins, amount)
assert result == expected, f"coins={coins}, amount={amount}, expected={expected}, got={result}"
print(f"coins={coins}, amount={amount} -> {result} ✓")
test_coin_change()
Common Mistakes
- Not handling impossible cases: Forgetting to return -1 when no solution exists
- Wrong initialization: Using 0 instead of infinity for impossible states
- Integer overflow: Using Integer.MAX_VALUE without checking for overflow
- Off-by-one errors: Incorrect loop bounds or array indexing
- Greedy assumption: Thinking largest coins first always works
- Base case errors: Not properly handling amount = 0
Follow-up Questions
- Coin Change II: Count the number of ways to make the amount
- Minimum coins with path: Return the actual coins used, not just the count
- Limited coins: What if each coin has a limited quantity?
- Multiple currencies: Handling different currency systems
- Optimization: Can we reduce space complexity further?
- Parallel processing: How to solve this problem in parallel?
Interview Tips
- Clarify constraints: Ask about coin denominations and amount ranges
- Start with examples: Work through small examples to understand the pattern
- Discuss approaches: Compare recursive vs iterative vs BFS solutions
- Handle edge cases: Make sure to cover impossible cases and amount = 0
- Optimize incrementally: Start with memoization, then move to tabulation
- Explain the recurrence: Clearly state the DP relationship
- Time/space tradeoffs: Discuss different approaches and their complexities