Jobs

Interviews

Discussions

Coin Change II

Medium

Microsoft

0 views

Topics:

Dynamic Programming

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

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

Constraints:

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

Coin Change II

Medium

Microsoft

0 views

Topics:

Dynamic Programming

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

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

Constraints:

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the amount and the values of the coins be zero or negative?
What is the expected return value if it is not possible to make up the amount with any combination of coins?
Are duplicate combinations considered distinct?
What are the maximum values for the amount and the number of coins?
Is the order of coins in the 'coins' array guaranteed to be sorted, or can it be in any order?

Brute Force Solution

Approach

The goal is to find how many different combinations of coins add up to a target amount. The brute force approach tries every single possible combination of coins, no matter how inefficient, to see if it reaches the target.

Here's how the algorithm would work step-by-step:

Start with no coins at all and see if that equals the target amount. If it does, that's one way to make the target (though probably not a useful one!).
Now, try using one of the coin types as many times as possible. For example, if you have pennies, try using only pennies to reach the target. If you can, that's another way.
Then, try combining different coin types. Start with one penny and see what other coins you need to reach the target. Then try two pennies, then three pennies, and so on, always adjusting the other coins to compensate.
Keep track of every single combination of coins you try and whether or not that combination adds up to exactly the target amount.
Continue experimenting with all possible combinations of coin types until you've exhausted all the possibilities. This means you've tried every conceivable mixture of pennies, nickels, dimes, quarters, etc.
Finally, count up the number of combinations you found that exactly match the target amount. That total count is the answer.

Code Implementation

def coin_change_brute_force(amount, coins):
    number_of_combinations = 0

    def find_combinations(current_amount, coin_index):
        nonlocal number_of_combinations

        # If current_amount equals to amount, increment the counter
        if current_amount == amount:
            number_of_combinations += 1
            return

        # If current_amount exceeds the amount, return
        if current_amount > amount:
            return

        # If we have used all the coins, return
        if coin_index >= len(coins):
            return

        # Explore combinations including the current coin
        find_combinations(current_amount + coins[coin_index], coin_index)

        # Explore combinations excluding the current coin
        find_combinations(current_amount, coin_index + 1)

    # Start with no coins and the first coin type
    find_combinations(0, 0)

    return number_of_combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(amount * number of coins) – The described brute-force approach explores all possible combinations of coins to reach the target amount. In the worst-case scenario, we might need to consider using each coin type many times. Imagine trying every possible count of each coin type up to the target amount. The number of times we explore different combinations to reach the amount will depend on the target 'amount' and how many coin types 'number of coins' we are given. Thus, the time complexity is proportional to the product of the target amount and the number of coin types, leading to O(amount * number of coins).

Space Complexity

O(1) – The brute force approach, as described, doesn't explicitly mention auxiliary data structures like arrays, hash maps, or sets. The explanation focuses on trying different combinations without storing them. It implicitly keeps track of the current combination being tested, which would involve a few integer variables representing the count of each coin type being used. These variables consume constant space regardless of the target amount or the number of coin types; hence, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the number of ways to make change for a certain amount of money using different coin denominations. Instead of brute-forcing every possible combination, we'll use a clever method to build up the solution piece by piece.

Here's how the algorithm would work step-by-step:

Imagine we have a table. One side represents the amount we want to make change for (from zero up to the target amount), and the other side represents the different coin denominations we can use.
We start by figuring out how many ways we can make change for zero using each coin denomination. There's always one way to make change for zero (using no coins).
Now, we go through each coin denomination one at a time. For each coin, we look at each amount from zero up to the target amount.
If the coin's value is less than or equal to the current amount, we have two options: either we don't use the coin at all, or we use it. The number of ways to make change for the amount is the sum of these two options.
If the coin's value is greater than the current amount, we can't use the coin, so the number of ways to make change for the amount is just the same as if we didn't have that coin.
We fill in the table this way, row by row, using each coin denomination in turn. The final answer is the number in the table at the cell representing the target amount and the last coin denomination.
By building up the solution incrementally, we avoid recalculating the same information over and over, making the process much faster.

Code Implementation

def coin_change_two(amount, coins):
    number_of_coins = len(coins)
    # dp[i][j] stores the number of ways to make amount j with first i coins
    dp_table = [[0] * (amount + 1) for _ in range(number_of_coins + 1)]

    # Base case: There's one way to make amount 0 (no coins).
    for i in range(number_of_coins + 1):
        dp_table[i][0] = 1

    for i in range(1, number_of_coins + 1):
        for current_amount in range(1, amount + 1):
            coin_value = coins[i - 1]

            # If the current coin's value is <= current amount.
            if coin_value <= current_amount:
                # Consider using the current coin or not using it.
                dp_table[i][current_amount] = dp_table[i - 1][current_amount] + dp_table[i][current_amount - coin_value]

            # If current coin's value > current amount.
            else:
                # Exclude the current coin; can't use it.
                dp_table[i][current_amount] = dp_table[i - 1][current_amount]

    # The answer is at dp[number_of_coins][amount]
    return dp_table[number_of_coins][amount]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(amount * coins.length) – The algorithm iterates through each coin denomination in the coins array using a loop, and for each coin, it iterates from 0 up to the target amount. Therefore, the time complexity depends on both the target amount and the number of coin denominations. If 'amount' is the target amount and 'coins.length' is the number of coin denominations, the number of operations roughly corresponds to visiting each cell in a 2D table of size (amount + 1) x (coins.length). Thus, the overall time complexity is O(amount * coins.length).

Space Complexity

O(amount) – The algorithm uses a table (which can be implemented as a 1D or 2D array, depending on optimization) to store the number of ways to make change for each amount from 0 up to the target amount. The size of this table is directly proportional to the target amount. Therefore, the auxiliary space required is proportional to the target amount, not the number of coin denominations. Thus, the space complexity is O(amount).

Edge Cases

Case	How to Handle
coins array is null or empty	Return 0 if the coins array is null or empty, as no combinations are possible.
amount is negative	Return 0 if the amount is negative, as it's impossible to make negative change.
amount is 0	Return 1 if the amount is 0, as there's one way to make change (using no coins).
coins array contains zero or negative values	Filter out any non-positive coin values before processing to avoid invalid combinations or infinite loops.
Large amount and large coin values can lead to integer overflow	Use a data type with larger capacity like 'long' to store the number of combinations to prevent overflow.
Very large coins array size	The DP table size will depend only on the amount, the time complexity will still increase depending on coin size.
No combination sums up to the amount	The algorithm returns 0 if no combination of coins sums up to the target amount after the DP table is fully processed.
Coins array contains duplicate values	The dynamic programming approach inherently handles duplicate coin values correctly as they are simply different paths to the same total.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the amount and the values of the coins be zero or negative?
What is the expected return value if it is not possible to make up the amount with any combination of coins?
Are duplicate combinations considered distinct?
What are the maximum values for the amount and the number of coins?
Is the order of coins in the 'coins' array guaranteed to be sorted, or can it be in any order?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with no coins at all and see if that equals the target amount. If it does, that's one way to make the target (though probably not a useful one!).
Now, try using one of the coin types as many times as possible. For example, if you have pennies, try using only pennies to reach the target. If you can, that's another way.
Then, try combining different coin types. Start with one penny and see what other coins you need to reach the target. Then try two pennies, then three pennies, and so on, always adjusting the other coins to compensate.
Keep track of every single combination of coins you try and whether or not that combination adds up to exactly the target amount.
Continue experimenting with all possible combinations of coin types until you've exhausted all the possibilities. This means you've tried every conceivable mixture of pennies, nickels, dimes, quarters, etc.
Finally, count up the number of combinations you found that exactly match the target amount. That total count is the answer.

Code Implementation

def coin_change_brute_force(amount, coins):
    number_of_combinations = 0

    def find_combinations(current_amount, coin_index):
        nonlocal number_of_combinations

        # If current_amount equals to amount, increment the counter
        if current_amount == amount:
            number_of_combinations += 1
            return

        # If current_amount exceeds the amount, return
        if current_amount > amount:
            return

        # If we have used all the coins, return
        if coin_index >= len(coins):
            return

        # Explore combinations including the current coin
        find_combinations(current_amount + coins[coin_index], coin_index)

        # Explore combinations excluding the current coin
        find_combinations(current_amount, coin_index + 1)

    # Start with no coins and the first coin type
    find_combinations(0, 0)

    return number_of_combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine we have a table. One side represents the amount we want to make change for (from zero up to the target amount), and the other side represents the different coin denominations we can use.
We start by figuring out how many ways we can make change for zero using each coin denomination. There's always one way to make change for zero (using no coins).
Now, we go through each coin denomination one at a time. For each coin, we look at each amount from zero up to the target amount.
If the coin's value is less than or equal to the current amount, we have two options: either we don't use the coin at all, or we use it. The number of ways to make change for the amount is the sum of these two options.
If the coin's value is greater than the current amount, we can't use the coin, so the number of ways to make change for the amount is just the same as if we didn't have that coin.
We fill in the table this way, row by row, using each coin denomination in turn. The final answer is the number in the table at the cell representing the target amount and the last coin denomination.
By building up the solution incrementally, we avoid recalculating the same information over and over, making the process much faster.

Code Implementation

def coin_change_two(amount, coins):
    number_of_coins = len(coins)
    # dp[i][j] stores the number of ways to make amount j with first i coins
    dp_table = [[0] * (amount + 1) for _ in range(number_of_coins + 1)]

    # Base case: There's one way to make amount 0 (no coins).
    for i in range(number_of_coins + 1):
        dp_table[i][0] = 1

    for i in range(1, number_of_coins + 1):
        for current_amount in range(1, amount + 1):
            coin_value = coins[i - 1]

            # If the current coin's value is <= current amount.
            if coin_value <= current_amount:
                # Consider using the current coin or not using it.
                dp_table[i][current_amount] = dp_table[i - 1][current_amount] + dp_table[i][current_amount - coin_value]

            # If current coin's value > current amount.
            else:
                # Exclude the current coin; can't use it.
                dp_table[i][current_amount] = dp_table[i - 1][current_amount]

    # The answer is at dp[number_of_coins][amount]
    return dp_table[number_of_coins][amount]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
coins array is null or empty	Return 0 if the coins array is null or empty, as no combinations are possible.
amount is negative	Return 0 if the amount is negative, as it's impossible to make negative change.
amount is 0	Return 1 if the amount is 0, as there's one way to make change (using no coins).
coins array contains zero or negative values	Filter out any non-positive coin values before processing to avoid invalid combinations or infinite loops.
Large amount and large coin values can lead to integer overflow	Use a data type with larger capacity like 'long' to store the number of combinations to prevent overflow.
Very large coins array size	The DP table size will depend only on the amount, the time complexity will still increase depending on coin size.
No combination sums up to the amount	The algorithm returns 0 if no combination of coins sums up to the target amount after the DP table is fully processed.
Coins array contains duplicate values	The dynamic programming approach inherently handles duplicate coin values correctly as they are simply different paths to the same total.