Leetcode 322: Coin Change [Solution]

This question seems to be very easy at first sight and the solution also comes up to mind, but believe me, you are going to guess it wrong if you are not familiar with Dynamic Programming. I also tried the first solution that came up to mind and that was the wrong one. I have mentioned the first and the correct solutions in this article.

Difficulty: Medium
Jump To:

• Problem Statement
• Explanation
• Solution
• Algorithm
• Explanation with an example
• Implementation

Problem Statement

Question: https://leetcode.com/problems/coin-change/

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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 3:

Input: coins = [1], amount = 0
Output: 0

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

Input: coins = [1], amount = 2
Output: 2

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Explanation

The problem is simple and relatable, we just need to break an amount into the change based on the coins we have, the special thing is that the number of coins in the change should be minimum i.e. there should not be any combination of coins available which has the number of coins less than your answer.

Solution

So the first solution that came up in my mind was a greedy approach that I will sort the coins in descending order based on their values and try to include the biggest coin because it will decrease the amount by a bigger value and that can be filled by smaller coins so I'll get the minimum number of coins solution. Like as in Example 1: coins = [1,2,5], amount = 11 so the sorted coins will be [5,2,1] now I'll include 5 first which results in 2 coins, and the rest amount is 11 - (5x2) = 1 which can be fulfilled by 1 coin so I'll be using 3 coins total. The code is below:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int ans=0;
        sort(coins.begin(), coins.end(), greater<int>());
        auto ptr = coins.begin();
        while(amount && ptr!=coins.end()){
            if(amount >= (*ptr)){
                ans += (amount/(*ptr));
                amount %= (*ptr);
            }
            ptr++;
        }
        return amount ? -1 : ans;
    }
};

BUT

BUT

BUT

This is not a correct solution, Let's look at a beautiful case coins=[9,6,5,1], amount=11. If I include 9 then the rest value is 2 which can be created by 2 1 coins, in this way I'll be using 3 coins but the correct solution is 2 coins which can be achieved using 2 coins 5 & 6.

So what should be the correct solution???

So let's understand the correct solution now. The problem occurred when we included the big element first what if we go for the solution in a subproblem manner? I mean let's try to achieve the solution for amount=1, then for amount=2 then for amount=3, and so on until we get the solution for the amount we want. The interesting thing in this is that whenever I'm trying to get the solution for n, I already have the solution for all the values below n which can be used.

Did you ask, how? So, let's understand that in this way, I will try to include each coin to make a value equals to the current amount, If I am able to include this coin then check if including this coin results in the minimum number of coins till now if yes then I'll include this coin else not. Now here this past data will help. We'll understand this with an example but before that let's see the algorithm first.

Algorithm:

1. Create an array dp to keep track of all the solution from 0 to amount
2. Fill this array with Maximum Value of Integer
3. For amount=0 we need 0 coins so set dp[0]=0
4. Now fill the array using the below loop from i=1 to the amount
   1. Try each coin one by one to create amount i using this coin j
      1. If the value of this coin is smaller or equal to i then do below else pick the next coin
      2. If this coin is included then the rest of the amount is i-coins[j]
      3. Now check if a solution exists for this amount i.e. dp[i-coins[j] != INT_MAX and including this coins gives better solution then the current one
      4. If yes then include this coin and replace dp[i] with new minimum value dp[i-coins[j] + 1
5. If dp[amount]=INT_MAX i.e there is no solution so return -1 else return dp[amount]

Time Complexity: O(amount * coins.length)
Space Complexity: O(amount)

Explanation of solution with an example:

Let's see this with the above example.

coins = [9, 6, 5, 1]
amount = 11

Below is the dp array after step-3:

Below is the screenshot of above dp array at various stage of the algorithm:

1. i=1, j=3, coins[j]=1: amount=1 can be achieved by using 1 1 coin so dp[1] becomes 1
2. i=2, j=3, coins[j]=1: amount=2 can be achieved by using 2 1 coins so dp[2] becomes 2
3. i=5, j=1, coins[j]=5: amount=5 can be achieved by using 5 1 coins but using 1 5 coin is better solution as rest = dp[5 - 5] = 0 so using current coin 5 means we will be using 0+1=1 coin so dp[5] becomes 1
4. i=6, j=1, coins[j]=5: amount=6 can be achieved by using 5 coin asrest = dp[6 - 5] = 1 so using current coin 5 means we will be using 1+1=2 coin so dp[6] becomes 2
5. i=6, j=2, coins[j]=6: amount=6 can be achieved by using 6 coin and it's a better solution as rest = dp[6 - 6] = 0 so using current coin 6 means we will be using 0+1=1 coin and it's lesser than current solution dp[6]=2 so dp[6] becomes 1
6. i=11, j=0, coins[j]=9: amount=9 can be achieved by using coin 9 as rest = dp[11 - 9] = 2 so using current coin 9 means we will be using 2+1=3 coin so dp[11] becomes 3
7. i=11, j=1, coins[j]=5: amount=11 can be achieved by using coin 5 as well and it's a better solution as rest = dp[11 - 5] = dp[6] = 1 so using current coin 5 means we will be using 1+1=2 coin and it's lesser than current solution dp[11]=3 so dp[11] becomes 2

Implementation

C++ Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // Initialize DP array with INT_MAX and dp[0]=0
        int dp[amount+1];
        dp[0]=0;
        for(int i=1;i<=amount;++i)
            dp[i] = INT_MAX;

        int len = coins.size();

        // Fill DP array from amount=1 to amount's actual value
        for (int i = 1; i <= amount; ++i)
        {
            // Try to include all the coins one by one
            for (int j = 0; j < len; ++j)
            {
                // If this coin is usable(value less than current amount)
                if(coins[j] <= i){
                    // What is the cost for rest of the amount
                    // If I use this coin
                    // eg. if amount=8 and coins[j]=5 then rest is min cost
                    // for 8-5 = 3
                    int rest = dp[i-coins[j]];
                    // If including this coin gives lesser value 
                    // than current min value then include it
                    if(rest != INT_MAX && rest+1<dp[i]){
                        // update min value for amount=i
                        dp[i] = rest+1;
                    }
                }
            }
        }
        return dp[amount]==INT_MAX ? -1 : dp[amount];
    }
};

Runnable C++ Code:

Cover Photo by Marc Schaefer on Unsplash