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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104Problem 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.
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].
This C solution uses an array dp initialized to INT_MAX except for dp[0] which is 0, signifying no coins are needed to make zero amount. For each possible amount, we iterate through each coin, updating dp[i] to be the minimum number of coins found so far that can make up i. The answer is dp[amount] unless it remains as infinity (in which case it is impossible to form the amount).
Time Complexity: O(n * m), where n is the amount and m is the number of coins.
Space Complexity: O(n), for the array dp.
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.
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.
Python
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.
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * m), where |
| Breadth-First Search (BFS) Approach | Time Complexity: Approximately O(n * m), comparable to standard BFS, where |
| Dynamic Programming (Complete Knapsack) | — |
| 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. |
Coin Change - Dynamic Programming Bottom Up - Leetcode 322 • NeetCode • 676,799 views views
Watch 9 more video solutions →Practice Coin Change with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor