In this guide, you will get 322. Coin Change LeetCode Solution with the best time and space complexity. The solution to Coin Change problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Time Complexity: O(|\texttt{coins}||\texttt{amount}|)
Space Complexity: O(|\texttt{amount}|)
322. Coin Change LeetCode Solution in C++
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// dp[i] := the minimum number of coins to make up i
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (const int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] = min(dp[i], dp[i - coin] + 1);
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}; /* code provided by PROGIEZ */
322. Coin Change LeetCode Solution in Java
class Solution {
public int coinChange(int[] coins, int amount) {
// dp[i] := the minimum number of coins to make up i
int[] dp = new int[amount + 1];
Arrays.fill(dp, 1, dp.length, amount + 1);
for (final int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
} // code provided by PROGIEZ
322. Coin Change LeetCode Solution in Python
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
# dp[i] := the minimum number Of coins to make up i
dp = [0] + [amount + 1] * amount
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return -1 if dp[amount] == amount + 1 else dp[amount] # code by PROGIEZ
