322. Coin Change - DP and BFS Solution

The problem

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.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

Approach overview

Problem Overview: Given a list of coin denominations and a target amount, compute the minimum number of coins required to make that amount. If the amount cannot be formed using the available coins, return -1. Each coin can be used unlimited times.

Approach 1: Dynamic Programming (O(n * amount) time, O(amount) space)

This problem fits the classic unbounded knapsack pattern. Build a DP array dp where dp[i] represents the minimum number of coins required to make amount i. Initialize dp[0] = 0 and set all other values to a large sentinel value. Iterate from 1 to amount, and for each value try every coin. If a coin c can contribute (i - c >= 0), update dp[i] = min(dp[i], dp[i - c] + 1). The key insight: once you know the best answer for smaller amounts, you can extend them to larger amounts. This bottom‑up table ensures each subproblem is solved exactly once. Time complexity is O(n * amount) where n is the number of coins, and space complexity is O(amount). This is the most common solution using Dynamic Programming.

Approach 2: Breadth-First Search (BFS) on Amount States (O(n * amount) time, O(amount) space)

Model the problem as a shortest-path search where each node represents a remaining amount. Start from the target amount and subtract coin values to generate new states. Each BFS level corresponds to using one additional coin. Use a queue to process states and a visited set to avoid revisiting the same remaining amount. When the search reaches 0, the current level count equals the minimum number of coins required. BFS works because every edge (adding a coin) has equal cost, so the first time you reach zero gives the optimal solution. The worst-case time complexity is O(n * amount) because each amount can be visited once and expanded by all coins. Space complexity is O(amount) for the queue and visited set. This approach is a graph perspective using Breadth-First Search and simple Array iteration over coin values.

Recommended for interviews: The bottom-up Dynamic Programming approach is what most interviewers expect. It demonstrates recognition of overlapping subproblems and optimal substructure. BFS is a solid alternative that shows you can model problems as shortest-path searches in a state graph. If you quickly mention both and implement the DP solution, you signal strong algorithmic understanding.

Approach 1: Dynamic Programming Approach

This approach dynamically computes the fewest number of coins needed for each amount from 0 to the target amount. You initialize an array dp where dp[i] represents the fewest number of coins needed to form amount i. Start with dp[0] = 0 since zero coins are needed to make the amount zero. For other amounts, assume infinity until proven otherwise. Iterate through each amount up to amount and each coin, updating dp accordingly. The solution lies in dp[amount].

Python

def coinChange(coins, amount):
    dp = [float('inf')] * (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] != float('inf') else -1

coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))

Java

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(sol.coinChange(coins, amount));
    }
}

C++

#include <vector>
#include <iostream>
#include <limits.h>

int coinChange(std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    std::cout << coinChange(coins, amount) << std::endl;
    return 0;
}

JavaScript

function coinChange(coins, amount) {
    let dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount));

#include <stdio.h>
#include <limits.h>

int coinChange(int* coins, int coinsSize, int amount) {
    int dp[amount + 1];
    for (int i = 0; i <= amount; i++) dp[i] = INT_MAX;
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coinsSize; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                dp[i] = dp[i] < (dp[i - coins[j]] + 1) ? dp[i] : (dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 11;
    printf("%d\n", coinChange(coins, 3, amount));
    return 0;
}

using System;

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            foreach (int coin in coins) {
                if (coin <= i && dp[i - coin] != int.MaxValue) {
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == int.MaxValue ? -1 : dp[amount];
    }
    public static void Main(string[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        Solution solution = new Solution();
        Console.WriteLine(solution.CoinChange(coins, amount));
    }
}

This Python solution constructs a list, dp, to store the minimum number of coins required to form each amount up to amount. Each value is initiated to float('inf') except for the zero amount which is zero. It iteratively updates possible amounts by considering each coin and updates the dp values accordingly to ensure the minimum is found.

Complexity

Time Complexity: O(n * m), where n is the desired amount and m is the number of provided coins.
Space Complexity: O(n), to hold the computed values of dp.

Try this approach in the editor

Approach 2: Breadth-First Search (BFS) Approach

This BFS-based method considers each step as a level, ensuring that every level in the search tree corresponds to adding a different coin denomination yielding a new amount. It is implemented using a queue initialized with the target amount, repeatedly generating the next possible amounts by subtracting each coin in turn until the amount is zero or deemed unreachable.

Python

from collections import deque

def coinChange(coins, amount):
    if amount == 0:
        return 0
    queue = deque([(amount, 0)])
    visited = set()
    while queue:
        current, steps = queue.popleft()
        for coin in coins:
            next_amount = current - coin
            if next_amount == 0:
                return steps + 1
            if next_amount > 0 and next_amount not in visited:
                visited.add(next_amount)
                queue.append((next_amount, steps + 1))
    return -1

coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))

This BFS solution uses a queue to attempt each feasible coin subtraction on a given amount. It initially pushes a pair into the queue: the current amount, and the number of steps (or coins) taken. The iteration through coins short-circuits when next_amount becomes zero, else it appends the resulting amounts — not yet checked — back into the queue.

Complexity

Time Complexity: Approximately O(n * m), comparable to standard BFS, where n is the amount and m is the number of coins. Actual time can be higher based on processed nodes.
Space Complexity: O(n), limited by queue and visited set sizes, corresponding to different amounts explored.

Try this approach in the editor

Approach 3: Dynamic Programming (Complete Knapsack)

We define f[i][j] as the minimum number of coins needed to make up the amount j using the first i types of coins. Initially, f[0][0] = 0, and the values of other positions are all positive infinity.

We can enumerate the quantity k of the last coin used, then we have:

$f[i][j] = min(f[i - 1][j], f[i - 1][j - x] + 1, cdots, f[i - 1][j - k times x] + k)

where x represents the face value of the i-th type of coin.

Let j = j - x, then we have:

f[i][j - x] = min(f[i - 1][j - x], f[i - 1][j - 2 times x] + 1, cdots, f[i - 1][j - k times x] + k - 1)

Substituting the second equation into the first one, we can get the following state transition equation:

f[i][j] = min(f[i - 1][j], f[i][j - x] + 1)

The final answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n$ are the number of types of coins and the total amount, respectively.

TypeScript

function coinChange(coins: number[], amount: number): number {
    const m = coins.length;
    const n = amount;
    const f: number[][] = Array(m + 1)
        .fill(0)
        .map(() => Array(n + 1).fill(1 << 30));
    f[0][0] = 0;
    for (let i = 1; i <= m; ++i) {
        for (let j = 0; j <= n; ++j) {
            f[i][j] = f[i - 1][j];
            if (j >= coins[i - 1]) {
                f[i][j] = Math.min(f[i][j], f[i][j - coins[i - 1]] + 1);
            }
        }
    }
    return f[m][n] > n ? -1 : f[m][n];
}

func coinChange(coins []int, amount int) int {
	m, n := len(coins), amount
	f := make([][]int, m+1)
	const inf = 1 << 30
	for i := range f {
		f[i] = make([]int, n+1)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if j >= coins[i-1] {
				f[i][j] = min(f[i][j], f[i][j-coins[i-1]]+1)
			}
		}
	}
	if f[m][n] > n {
		return -1
	}
	return f[m][n]
}

Rust

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let n = amount as usize;
        let mut f = vec![n + 1; n + 1];
        f[0] = 0;
        for &x in &coins {
            for j in x as usize..=n {
                f[j] = f[j].min(f[j - (x as usize)] + 1);
            }
        }
        if f[n] > n {
            -1
        } else {
            f[n] as i32
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n * m), where `n` is the desired amount and `m` is the number of provided coins. Space Complexity: O(n), to hold the computed values of `dp`.
Breadth-First Search (BFS) Approach	Time Complexity: Approximately O(n * m), comparable to standard BFS, where `n` is the amount and `m` is the number of coins. Actual time can be higher based on processed nodes. Space Complexity: O(n), limited by queue and visited set sizes, corresponding to different amounts explored.
Dynamic Programming (Complete Knapsack)	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming (Bottom-Up)	O(n * amount)	O(amount)	General case and most interview settings. Efficient and straightforward for unbounded coin problems.
Breadth-First Search (State Graph)	O(n * amount)	O(amount)	Useful when modeling the problem as shortest path where each coin addition represents one step.

Frequently asked questions

Is Coin Change easy or hard?

Coin Change is generally considered a medium difficulty problem. The challenge lies in recognizing the dynamic programming pattern and correctly defining the state transition for the minimum number of coins.

How to solve Coin Change in O(n * amount)?

Create a DP array where dp[i] represents the minimum coins needed to form amount i. Initialize dp[0] = 0 and fill the rest with a large value. For each amount i, iterate through all coins and update dp[i] = min(dp[i], dp[i - coin] + 1) if the coin fits. The final answer is dp[amount], or -1 if it remains unreachable.

What is the best approach for Coin Change?

Dynamic Programming is the most widely used solution for Coin Change. A bottom-up DP array stores the minimum coins needed for every amount from 0 to the target. This guarantees the optimal answer with O(n * amount) time and O(amount) space, where n is the number of coin denominations.

What data structure is used in Coin Change?

The most common solution uses a one-dimensional array for dynamic programming. BFS-based solutions additionally use a queue and a visited set to track explored remaining amounts during the search.

What is the time complexity of Coin Change?

The optimal dynamic programming solution runs in O(n * amount) time because each amount from 1 to the target is computed by iterating through all coin denominations. Space complexity is O(amount) for the DP array that stores intermediate results.

Coin Change Python or Java solution approach?

Both Python and Java implementations typically use the same bottom-up DP strategy. Initialize an array of size amount + 1, update values using each coin denomination, and return the computed minimum for the target amount.

Is Coin Change asked at Google, Amazon, or Meta?

Coin Change and its variations frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of dynamic programming, state transitions, and optimization over subproblems.

Coin Change solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Breadth-First Search (BFS) Approach

Approach 3: Dynamic Programming (Complete Knapsack)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Coin Change solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Breadth-First Search (BFS) Approach

Approach 3: Dynamic Programming (Complete Knapsack)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems