Coin Change
Coin Change:
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 2:
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
Try this Problem on your own or check similar problems:
- Minimum Number of Operations to Convert Time
- Minimum Cost For Tickets
- Maximum Value of K Coins From Piles
Solution:
- Java
- JavaScript
- Python
- C++
public int coinChange(int[] coins, int amount) {
int[] dp = new int [amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for(int i = 1; i <= coins.length; ++i){
for(int j = 1; j <= amount; ++j){
if(j >= coins[i-1]){
dp[j] = Math.min(dp[j], dp[j-coins[i-1]] + 1);
}
}
}
return dp[amount] > amount ? - 1 : dp[amount];
}
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let i = 1; i <= coins.length; i++) {
for (let j = 1; j <= amount; j++) {
if (j >= coins[i - 1]) {
dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
};
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, len(coins) + 1):
for j in range(1, amount + 1):
if j >= coins[i - 1]:
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1)
return -1 if dp[amount] > amount else dp[amount]
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= coins.size(); i++) {
for (int j = 1; j <= amount; j++) {
if (j >= coins[i - 1]) {
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
Time/Space Complexity:
- Time Complexity: O(amount * S) where
S = coins.length - Space Complexity: O(amount)
Explanation:
This is an example of Unbounded Knapsack, we can take unlimited quantities of each of the items to get the result (sum) we want. So, we have two decisions either take the element or skip it. How do we decide if we should take it or not? Well, we want to minimize the number of coins. If we have matrix dp than dp[i][j] represents the least coins we can use (it includes coins[0..i]) for the sum j, so the last element dp[coins.length][amount] will tell use what's the minimum number of coins (all coins from input array) we can add to get sum amount. Since we're minimizing each time we're picking the result with fewer coins Math.min(dp[i-1][j], dp[i][j-coins[i-1]] + 1) (we choose to not use the current coin for the sum j, or we pick it as +1 coin to the sum j-coins[i-1]). What will be our first-row values? Well, since we're minimizing our matrix to produce any useful information, we need to have larger numbers in the first row (think of them as triggers/activations of the formula calculation down the matrix). For the marker we choose amount+1, since if we have amount = X the largest number of coins we can use to get it are the coins with value/weight 1 so we need X of 1's and that's the maximum, so a good marker would be X+1.
- Java
- JavaScript
- Python
- C++
public int coinChange(int[] coins, int amount) {
int[][] dp = new int [coins.length + 1][amount + 1];
for(int i = 0; i <= coins.length; ++i){
dp[i][0] = 0;
}
for(int i = 1; i <= amount; ++i){
dp[0][i] = amount + 1;
}
for(int i = 1; i <= coins.length; ++i){
for(int j = 1; j <= amount; ++j){
dp[i][j] = j >= coins[i-1] ? Math.min(dp[i-1][j], dp[i][j-coins[i-1]] + 1) : dp[i-1][j];
}
}
return dp[coins.length][amount] > amount ? -1 : dp[coins.length][amount];
}
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
const dp = new Array(coins.length + 1)
.fill(0)
.map(() => new Array(amount + 1));
for (let i = 0; i <= coins.length; ++i) {
dp[i][0] = 0;
}
for (let i = 1; i <= amount; ++i) {
dp[0][i] = amount + 1;
}
for (let i = 1; i <= coins.length; ++i) {
for (let j = 1; j <= amount; ++j) {
dp[i][j] =
j >= coins[i - 1]
? Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
: dp[i - 1][j];
}
}
return dp[coins.length][amount] > amount ? -1 : dp[coins.length][amount];
};
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
for i in range(len(coins) + 1):
dp[i][0] = 0
for i in range(1, amount + 1):
dp[0][i] = amount + 1
for i in range(1, len(coins) + 1):
for j in range(1, amount + 1):
dp[i][j] = dp[i - 1][j]
if j >= coins[i - 1]:
dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1)
return -1 if dp[len(coins)][amount] > amount else dp[len(coins)][amount]
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1));
for (int i = 0; i <= coins.size(); ++i) {
dp[i][0] = 0;
}
for (int i = 1; i <= amount; ++i) {
dp[0][i] = amount + 1;
}
for (int i = 1; i <= coins.size(); ++i) {
for (int j = 1; j <= amount; ++j) {
dp[i][j] = j >= coins[i - 1] ? min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1) : dp[i - 1][j];
}
}
return dp[coins.size()][amount] > amount ? -1 : dp[coins.size()][amount];
}
};
Can we optimize this further? Yep, we can reduce the space complexity by reducing the dimensionality of the helper array since we only need the element from the previous row (not all rows) for each of our calculations. The final solution is given in the Solution section.