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:

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:

     f[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.

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

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.