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 <= 104The Coin Change problem asks for the minimum number of coins required to make a given amount using an unlimited supply of provided coin denominations. A common way to think about it is through Dynamic Programming. The idea is to build solutions for smaller amounts and reuse them to compute larger ones. Using a dp array where dp[i] represents the minimum coins needed for amount i, we iteratively update values using previously computed states.
Another perspective uses Breadth-First Search (BFS). Treat each reachable amount as a node in a graph and each coin as an edge that increases the total. BFS explores amounts level by level, where each level corresponds to using one more coin. The first time the target amount is reached gives the minimum number of coins.
The DP approach typically runs in O(n × amount) time where n is the number of coin types, while maintaining an array of size amount + 1. BFS offers a conceptual alternative with similar worst‑case complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming | O(n × amount) | O(amount) |
| Breadth-First Search | O(n × amount) | O(amount) |
NeetCode
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].
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.
1using System;
2
3public class Solution {
4 public int CoinChange(int[] coins, int amount) {
5 int[] dp = new int[amount + 1];
6 Array.Fill(dp, int.MaxValue);
7 dp[0] = 0;
8 for (int i = 1; i <= amount; i++) {
9 foreach (int coin in coins) {
10 if (coin <= i && dp[i - coin] != int.MaxValue) {
11 dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
12 }
13 }
}
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 C# solution declares an array dp initialized to containing int.MaxValue for each element, where zero coins are needed to form amount zero. Iterating through each potential amount, the array is updated to reflect the minimum number of coins needed by considering each coin in turn. If dp[amount] remains as int.MaxValue, return -1; otherwise, return the value in dp[amount].
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.
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.
1from collections import deque
2
3def coinChange(coins, amount
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Coin Change can also be modeled as a graph problem and solved using Breadth-First Search. Each level in the BFS represents adding one more coin, and reaching the target amount for the first time guarantees the minimum number of coins.
Yes, Coin Change and its variations are common interview questions at top tech companies. They test understanding of dynamic programming, state transitions, and optimization strategies.
The most common optimal approach uses dynamic programming. It builds the minimum number of coins required for every value from 0 up to the target amount, reusing previously computed results. This ensures an efficient O(n × amount) time solution.
The typical solution uses an array or list for dynamic programming to store minimum coins required for each amount. In the BFS approach, a queue is used to explore reachable amounts level by level.
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.