322. Coin Change

MediumBreadth-First SearchArrayDynamic Programming
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

How does quick sort divide the problem into subproblems?

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:

  1. Initialize DP table: Create an array f with a size of amount + 1. The first element f[0] is set to 0 since no coins are needed to make an amount of 0. All other elements are set to inf (which represents a large number larger than any real coin count, used to indicate 'not possible' initially).

  2. Algorithm loop:

    • Iterate through each of the coin denominations x provided in the coins array.
    • For each coin denomination x, run an inner loop from x to amount (inclusive).
    • In the inner loop, update the DP table f at each amount j (where j ranges from x to amount) using the formula: 
      1f[j] = min(f[j], f[j - x] + 1)
      What this does is check if using the current coin x results in a smaller coin count for the amount j than the one we've previously found (if any). We compare the existing number of coins for amount j (f[j]), and the number of coins for j - x plus one (f[j - x] + 1 since we add one coin of denomination x).

  3. Final decision:

    • After the DP table is filled, we check the value of f at index amount (which represents the amount we want to make).
    • If f[amount] is still set to inf, 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 (not inf), it represents the minimum number of coins needed to make the amount, and we return this value as our answer.

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), where n is the amount, as it only requires an array of size amount + 1.
  • Time complexity is O(m*n), where m is the number of coin denominations, and n is the amount, due to the nested loops iterating over each coin and each amount respectively.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have coins = [1, 3, 4] and the amount = 6.

  1. We initialize the DP table f with amount + 1 (7) slots: f = [0, inf, inf, inf, inf, inf, inf]. The first element f[0] is 0 because no coins are needed to make an amount of 0.

  2. Now we iterate through the coin denominations:

    a. For x = 1: - We iterate from 1 to amount (6). - At each j, we update f[j] = min(f[j], f[j - x] + 1). - After the loop, f looks like: [0, 1, 2, 3, 4, 5, 6]. For any j, at most j coins of denomination 1 are needed.

    b. For x = 3: - We iterate from 3 to 6. - We update f[3] to 1, f[4] to 2, f[5] to 2, and f[6] to 2, because for each of these amounts, using a 3-denomination coin is more efficient. - f now is: [0, 1, 2, 1, 2, 2, 2].

    c. For x = 4: - We iterate from 4 to 6. - We update f[4] to 1, and f[6] to 2 (f[5] remains 2 as f[5 - x] is inf), which uses one coin of 4 and then utilizes previous results for remaining amount 2. - f now looks like: [0, 1, 2, 1, 1, 2, 2].

  3. Our final DP table is [0, 1, 2, 1, 1, 2, 2]. Looking at the value of f[6], we see 2, which means the minimum number of coins needed to make the amount 6 is 2. This would correspond to using coins 4 and 2, which are both subsets of our initial coins array (with 2 being the sum of two 1 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
Not Sure What to Study? Take the 2-min Quiz

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

BFS Fundamentals

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

Dynamic Programming Introduction and Patterns

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«