322. Coin Change
Problem Description
You have an array coins
that contains different coin denominations and an integer amount
which represents the total amount of money you want to make with these coins. The task is to calculate the minimum number of coins needed to make up the given amount. If it's not possible to reach the amount
with the given coin denominations, the function should return -1
.
You can use each type of coin as many times as you want; in other words, there's an unlimited supply of each coin.
Flowchart Walkthrough
Let's solve the algorithm choice for leetcode 322. Coin Change using the Flowchart. Here's how we proceed with the question:
Is it a graph?
- Yes: Although at first glance it doesn't seem like a typical graph problem, we can think about it as a graph where each state represents an amount of money, and each state/vertex connects to another state that represents a subtraction of one coin denomination from the current amount.
Is it a tree?
- No: The graph potentially has multiple ways to arrive at the same state (amount of money) by using different series of coin denominations.
Is the problem related to directed acyclic graphs (DAGs)?
- No: Coin change is more of a dynamic programming/state transition problem, which doesn't particularly involve properties like topological sorting of nodes which are typical in DAGs.
Is the problem related to shortest paths?
- Yes: Finding the minimum number of coins that make up a certain amount can be treated as finding the shortest path in an unweighted graph where each edge represents using a single coin to get to a new amount.
Is the graph weighted?
- No: Each step from one amount to a lesser amount (by subtracting one coin denomination) can be considered as an unweighted step, with each step (coin usage) having equal 'weight' or cost in terms of the progression toward the goal.
Conclusion: The flowchart suggests using BFS for this unweighted shortest path problem to find the minimum number of coins needed for making the exact amount.
Intuition
The intuition behind the solution is based on a classic algorithmic problem, known as the Coin Change problem, which can be solved using Dynamic Programming (DP). The idea is to build up the solution by solving for smaller subproblems and then use those solutions to construct the answer for the larger problem.
The approach used is called "bottom-up" DP. We initialize an array f
of size amount + 1
, where each element f[i]
will hold the minimum number of coins needed to make the sum i
. We start with f[0] = 0
since no coins are needed to achieve a total amount of 0.
We set all other values in f
to inf
(infinity) which signifies that initially, we assume it's impossible to make those amounts with any combination of the coins given.
Next, we iterate through each coin denomination, x
. For each x
, we go through the f
array starting from f[x]
to f[amount]
trying to update the minimum number of coins needed for each amount j
by considering the number of coins needed for j - x
plus one more coin of denomination x
. The inner loop uses the formula f[j] = min(f[j], f[j - x] + 1)
to decide whether we have found a new minimum for amount j
.
After filling up the f
array, if f[amount]
is still inf
, that means it's not possible to form amount
with the given coins, and we return -1
. Otherwise, f[amount]
will hold the fewest number of coins needed to make up the amount
, and that's our answer.
Learn more about Breadth-First Search and Dynamic Programming patterns.
Solution Approach
The solution is implemented using a dynamic programming approach, which effectively breaks down the problem of finding the minimum number of coins into smaller subproblems.
Here's a step-by-step breakdown of how the implementation works:
-
Initialize DP table: Create an array
f
with a size ofamount + 1
. The first elementf[0]
is set to 0 since no coins are needed to make an amount of 0. All other elements are set toinf
(which represents a large number larger than any real coin count, used to indicate 'not possible' initially). -
Algorithm loop:
- Iterate through each of the coin denominations
x
provided in thecoins
array. - For each coin denomination
x
, run an inner loop fromx
toamount
(inclusive). - In the inner loop, update the DP table
f
at each amountj
(wherej
ranges fromx
toamount
) using the formula:
What this does is check if using the current coinf[j] = min(f[j], f[j - x] + 1)
x
results in a smaller coin count for the amountj
than the one we've previously found (if any). We compare the existing number of coins for amountj
(f[j]
), and the number of coins forj - x
plus one (f[j - x] + 1
since we add one coin of denominationx
).
- Iterate through each of the coin denominations
-
Final decision:
- After the DP table is filled, we check the value of
f
at indexamount
(which represents the amount we want to make). - If
f[amount]
is still set toinf
, it means we could not find a combination of coins to make up the amount, hence we return-1
. - If
f[amount]
has a definite number (notinf
), it represents the minimum number of coins needed to make the amount, and we return this value as our answer.
- After the DP table is filled, we check the value of
The dynamic programming pattern used here is known as the Bottom-Up approach as we start solving for the smallest possible amount and build our way up to the desired amount
, using previously computed values to find the next. This allows solving complex problems by combining the solutions of simpler subproblems.
The algorithm leverages the fact that reaching a smaller amount j - x
efficiently and adding one more coin of x
to it might be the optimal solution for a larger amount j
.
Efficiency:
- Space complexity is
O(n)
, wheren
is theamount
, as it only requires an array of sizeamount + 1
. - Time complexity is
O(m*n)
, wherem
is the number of coin denominations, andn
is theamount
, due to the nested loops iterating over each coin and each amount respectively.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have coins = [1, 3, 4]
and the amount = 6
.
-
We initialize the DP table
f
withamount + 1 (7)
slots:f = [0, inf, inf, inf, inf, inf, inf]
. The first elementf[0]
is0
because no coins are needed to make an amount of0
. -
Now we iterate through the coin denominations:
a. For
x = 1
: - We iterate from1
toamount (6)
. - At eachj
, we updatef[j] = min(f[j], f[j - x] + 1)
. - After the loop,f
looks like:[0, 1, 2, 3, 4, 5, 6]
. For anyj
, at mostj
coins of denomination1
are needed.b. For
x = 3
: - We iterate from3
to6
. - We updatef[3]
to1
,f[4]
to2
,f[5]
to2
, andf[6]
to2
, because for each of these amounts, using a3
-denomination coin is more efficient. -f
now is:[0, 1, 2, 1, 2, 2, 2]
.c. For
x = 4
: - We iterate from4
to6
. - We updatef[4]
to1
, andf[6]
to2
(f[5]
remains2
asf[5 - x]
isinf
), which uses one coin of4
and then utilizes previous results for remaining amount2
. -f
now looks like:[0, 1, 2, 1, 1, 2, 2]
. -
Our final DP table is
[0, 1, 2, 1, 1, 2, 2]
. Looking at the value off[6]
, we see2
, which means the minimum number of coins needed to make the amount6
is2
. This would correspond to using coins4
and2
, which are both subsets of our initialcoins
array (with2
being the sum of two1
coins).
We return the minimum number of coins found, which is 2
. This is the least amount of coins that can make 6
with the denominations given.
Solution Implementation
1from typing import List
2
3class Solution:
4 def coinChange(self, coins: List[int], amount: int) -> int:
5 # Initialize the maximum number of coins to a value greater than any possible coin number
6 MAX = float('inf')
7
8 # dp[i] will be storing the minimum number of coins required for amount i
9 # dp[0] is 0 because no coins are needed for the amount 0
10 dp = [0] + [MAX] * amount
11
12 # Traverse through all the amounts from 1 to amount inclusive
13 for coin in coins: # For each coin
14 for current_amount in range(coin, amount + 1):
15 # Update the dp table by comparing the current value
16 # with the value if we include the current coin
17 dp[current_amount] = min(dp[current_amount], dp[current_amount - coin] + 1)
18
19 # If we have not found a combination to form the amount
20 # then dp[amount] will still be MAX
21 return -1 if dp[amount] == MAX else dp[amount]
22
23# Example usage:
24# sol = Solution()
25# print(sol.coinChange([1, 2, 5], 11)) # Output: 3 (11 can be made with three 3 coins: 5+5+1)
26
1class Solution {
2 public int coinChange(int[] coins, int amount) {
3 // Define a large value which would act as our "infinity" substitute.
4 final int INF = 1 << 30;
5
6 // 'dp' will hold our optimal solutions to sub-problems, dp[i] will store the minimum number of coins needed to make amount 'i'.
7 int[] dp = new int[amount + 1];
8
9 // Initialize the dp array with INF to signify that those amounts are currently not achievable with the given coins.
10 Arrays.fill(dp, INF);
11
12 // Base case initialization: No coins are needed to make an amount of 0.
13 dp[0] = 0;
14
15 // Iterate over each type of coin available.
16 for (int coin : coins) {
17 // For each coin, try to build up to the target amount, starting from the coin's value itself up to 'amount'.
18 for (int currentAmount = coin; currentAmount <= amount; ++currentAmount) {
19 // Check if the current coin can contribute to a solution for 'currentAmount'.
20 // If so, update dp[currentAmount] to the minimum value between its current and the new possible number of coins used.
21 dp[currentAmount] = Math.min(dp[currentAmount], dp[currentAmount - coin] + 1);
22 }
23 }
24
25 // Return the answer for the target 'amount'. If dp[amount] is still INF, then it was not possible to make the amount using the given coins.
26 return dp[amount] >= INF ? -1 : dp[amount];
27 }
28}
29
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7 // Function to find the minimum number of coins needed to make up a given amount.
8 // coins: The denominations of the available coins.
9 // amount: The total amount for which we need to find the minimum coins.
10 int coinChange(vector<int>& coins, int amount) {
11 // Create vector with size amount + 1 to store minimum coins required for each total amount.
12 vector<int> minCoins(amount + 1, INT_MAX);
13 // Base case: 0 coins are needed for amount 0.
14 minCoins[0] = 0;
15
16 // Iterate over all coin denominations.
17 for (int coin : coins) {
18 // For each coin, compute min coins needed for all amounts from coin value up to the given amount.
19 for (int currentAmount = coin; currentAmount <= amount; ++currentAmount) {
20 // If it's possible to use coin to reach currentAmount, update minCoins for currentAmount.
21 if (minCoins[currentAmount - coin] != INT_MAX) {
22 minCoins[currentAmount] = min(minCoins[currentAmount], minCoins[currentAmount - coin] + 1);
23 }
24 }
25 }
26
27 // If minCoins for the given amount is still INT_MAX, return -1 as it's not possible to form the amount with given coins.
28 // Otherwise, return the minCoins for the given amount.
29 return minCoins[amount] == INT_MAX ? -1 : minCoins[amount];
30 }
31};
32
1// Function to find the fewest number of coins needed to make up a given amount
2// coins: an array of the coin denominations
3// amount: the total amount to make up with the coins
4function coinChange(coins: number[], amount: number): number {
5 // Initialize the number of coins needed for each amount up to 'amount'
6 const maxAmount = amount;
7 const minCoinsNeeded: number[] = Array(maxAmount + 1).fill(Number.MAX_SAFE_INTEGER);
8
9 // Base case: 0 coins are needed to make amount 0
10 minCoinsNeeded[0] = 0;
11
12 // Loop through each coin denomination
13 for (const coin of coins) {
14 // Update the minCoinsNeeded array for each amount from coin to maxAmount
15 for (let currentAmount = coin; currentAmount <= maxAmount; ++currentAmount) {
16 // Calculate the minimum number of coins needed for currentAmount
17 minCoinsNeeded[currentAmount] = Math.min(
18 minCoinsNeeded[currentAmount],
19 minCoinsNeeded[currentAmount - coin] + 1
20 );
21 }
22 }
23
24 // If the amount is larger than the maxAmount, it's not possible to make change
25 return minCoinsNeeded[maxAmount] > maxAmount ? -1 : minCoinsNeeded[maxAmount];
26}
27
Time and Space Complexity
The given Python code represents a dynamic programming solution for the coin change problem, where coins
is a list of distinct integer coin denominates and amount
is the total amount of money we need to make change for. Below is the analysis of the time and space complexity of this solution:
Time Complexity
The time complexity of the algorithm is O(S * n)
, where S
is the amount
to make change for, and n
is the number of different coin denominations available. This is because for each coin denomination, we iterate over all the values from the coin's value up to the amount, incrementally computing the fewest number of coins needed to make change for each value.
Space Complexity
The space complexity of the algorithm is O(S)
, where S
is the amount
to make change for. This is due to the auxiliary space used by the list f
which contains S + 1
elements, where f[i]
represents the fewest number of coins needed to make change for the amount i
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!