🪙322. Coin Change
Medium | Grind 75 | July 10, 2022
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: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1The way I first approached this problem was using two recursive calls whereby the first recursive call is made with the coin that can be used meaning the amount - coin is not negative. In this recursive call, the next coin used is the same. The second recursive call would be if you did not use the current coin. In your recursive call, you use the next coin. However, after looking at the discussions, I realized this could be solved easily using dynamic programming (DP).
The main idea behind the DP solution is to calculate the least amount of coins needed for all the numbers less than the amount. You start with 0. You know that if the amount is zero, there are no coins that can make up zero. Therefore we initialize the first value of our DP array with zero. DP array will store the least number of coins required for each amount: 0 -> target amount. The rest of the values for the DP array is initialized as INF. When we first start we will assume that it takes an infinite amount of coins to make up the amount.
Once we have initialized the DP, we will first iterate from 1 to the target amount. During each iteration, we will also iterate over all the coins in our coin array to find the least number of coins required to make up that amount.
SOLUTION
Example 1
Amount: 1 -> So we initialized 0 amount as needing 0 coins in our DP array. Next is amount 1. For amount 1, we have three possible coin choices. We have coin 1 which makes up amount 1 perfectly using 1 coin. The way we calculate this is by subtracting the amount - the coin. 1 - 1 gives us 0. We initialized our dp[0] to 0. Therefore, it takes 0 + 1(current coin) to make up the amount 1 using coin 1. Coins 3 and 5 cannot make up amount 1 so then we know it takes 1 coin to make up amount 1. We update our DP array [1] as 1.
Amount: 2 -> To make up 2, we subtract 2 from the different coins we have. If none of the coins can make up the amount, we leave the DP array untouched. We first take coin 1. When we subtract the amount from coin 1, we get the answer as 1. Since we have already calculated how many coins it takes to make up amount 1, we add dp[1](holds the least number of coins required to make up amount 1) + 1 (this current coin). We use coin 1 at the beginning and the value of dp[1] is 1, so, in total, we use 2 coins. We will temporarily store this value in the list since we don't know if this is the minimum number of coins required. The next coin is 2. When we subtract amount 2 from coin 2, we get 0. We now look at our dp[0] to see how many coins it takes to make up 0. This takes 0 coins and since we used coin 2 once (current coin), the total amount of coins used is 0 + 1 which is 1. We will add this value 1 to our temporary list. With coin 5, we know that we cannot make up amount 2 so we do nothing in our loop. Now that we have iterated over all the coins, we see what the minimum value in our temporary list is because that's the least amount of coins needed to make up that amount. This turns out to be 1. so our dp[2] = 1.
Amount: 3 -> For amount 3, we first take coin 1. Subtract 3 -1 and we get 2. We now check how many minimum coins it takes to get an amount of 2. Since we just computed that (dp[2]) we know it takes 1 coin to get amount 2. And since we currently used coin 1 once, the total coin used is 2. Now we use coin 2, subtract 3 - 2 and we get 1. dp[1] = 1, and since we currently used coin 2 once, the total number of coins used is 2. Since coin 5 cannot make up 3, we don't do anything. The minimum coin required in this case is 2, so we update dp[3] = 2.
This continues until we get to the amount 11. We will continue to build the least amount of coins required for every amount 4,5,6,7,8,9,10 and 11. The final answer to the question will be stored in our dp[11] since this is the value for the least amount of coins required to make up amount 11.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
INF= float('inf') #max value.
# array of size amount with max float as our value except for 0 index.
# ever index refers to min coin required to make the index amount.
dp = [0] + [INF] * amount
# Calculate min coin for every amount from 1 till target amount
for i in range(1, amount+1):
# hold all valid amount of coins that can make up the amount.
temp = []
#iterate over all the coins.
for c in coins:
if i - c < 0: # coin is larger than amount, ignore the coin.
continue
temp.append(dp[i-c]) # valid number of coins that make up amount.
if temp: # there are certain number of coins that make up the amount
# minimum number of coins making up amount.
#You add 1 because the current coin subtracted needs to be counted.
dp[i] = min(temp) + 1
if dp[amount] != INF: # valid number of coins that make up amount.
return dp[amount]
return -1
TIME AND SPACE COMPLEXITY
TIME: O(amount * N) where N is the number of coins. We iterate from 1 till the amount. Then within each iteration we iterate over all the coins. Therefore we get amount x n
SPACE: our DP array takes atmost "Amount" spaces. But the most spaces used is the temp array. In the worstt case scenario, every coin makes up the amount so for every amount, we use N spaces where N is the number of coins. Therefore, the worst case space complexity is O(amount * N)
Last updated