Jobs

Interviews

Discussions

Coin Change

Medium

Adobe

1 view

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 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

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

Coin Change

Medium

Adobe

1 view

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 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

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

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 `coins` array contain denominations of 0, or negative values?
What is the maximum possible value for `amount` and the number of coins in the `coins` array?
If there are multiple combinations of coins that result in the minimum number, is any one acceptable?
If `amount` is 0, should I return 0 or is that an invalid input?
Are duplicate coin denominations allowed in the `coins` array, and if so, how should they be handled?

Brute Force Solution

Approach

The brute force approach to solving coin change involves exploring every single possible combination of coins to reach the target amount. It’s like trying every way you can think of to add coins together until you find the right amount. If we find a combination, we record it, and at the end we know the fewest coins we can use.

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

Start by trying to make the amount using only the largest coin.
See how many of those coins fit, and if it's exactly the target amount, we're done! That is one way to make change.
If it's more than the target, it doesn't work, so discard this attempt and try something different.
If it's less than the target, figure out how much is left, and then try all combinations of the other coins to make up the remaining amount. For example, maybe use the next largest coin. Maybe use two of them.
Keep trying different numbers of the largest coin combined with all possible numbers of the other coins.
Repeat the previous step by trying all combinations of second largest coin combined with all possible numbers of the other coins
Each time we find a combination of coins that equals the target amount, record the number of coins used in that combination.
Once we've tried absolutely every possible combination of every coin type, compare all the successful combinations we found.
Choose the combination that uses the fewest coins. That's the answer!

Code Implementation

def coin_change_brute_force(coins, amount):
    minimum_number_of_coins = float('inf')

    def find_minimum_coins(remaining_amount, current_coin_count):
        nonlocal minimum_number_of_coins

        if remaining_amount == 0:
            minimum_number_of_coins = min(minimum_number_of_coins, current_coin_count)
            return

        if remaining_amount < 0:
            return

        # Iterate through each coin denomination
        for coin in coins:

            # Recursively explore the solution space by subtracting the coin
            # from the remaining amount and incrementing the coin count
            find_minimum_coins(remaining_amount - coin, current_coin_count + 1)

    find_minimum_coins(amount, 0)

    # If no combination was found, return -1
    if minimum_number_of_coins == float('inf'):
        return -1

    return minimum_number_of_coins

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(amount^number_of_coins) – The brute force coin change algorithm explores every possible combination of coins to reach the target amount. In the worst-case scenario, we might need to check all possible combinations of each coin denomination, leading to exponential growth. The number of possible combinations roughly corresponds to the amount raised to the power of the number of coin types available. Thus, the time complexity grows exponentially with the target amount and the number of coin denominations.

Space Complexity

O(N^M) – The brute force approach, as described, explores all possible combinations of coins. Implicitly, the algorithm needs to keep track of these combinations as it explores them. In the worst-case scenario, the recursion depth is proportional to the target amount N and the number of coin denominations M. Each level of the recursion stack represents a decision of how many of each coin to use, leading to a branching factor dependent on the number of coin denominations and the target amount. Thus the maximum depth and branching could lead to a space complexity of O(N^M) as the algorithm explores the call stack. This considers N to be the target amount and M the number of denominations.

Optimal Solution

Approach

The best way to figure out the fewest coins needed is to solve smaller problems first and build up to the final answer. Imagine having a chart where each spot represents an amount of money, and we fill it in gradually using only the available coins. This ensures we're reusing previous calculations to avoid redundant work, giving us a quick and efficient final answer.

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

Create a table to store the minimum number of coins needed for each amount from zero up to the target amount.
Start with an amount of zero, which requires zero coins.
For each coin value we have, go through our table. If the coin is less than or equal to the current amount we're considering, we can potentially use it.
Figure out how many coins it would take to reach the current amount if we used this coin. This will equal to '1 plus the number of coins for the remaining amount if we use this coin'.
Store the minimum number of coins to reach that amount. We keep updating a spot until we find the very best solution.
Repeat this for all the available coins and all the amounts.
After considering all possibilities, the final value in the table, at the spot that represents the target amount, will be the minimum number of coins needed.

Code Implementation

def coin_change(coins, amount):
    minimum_number_of_coins = [float('inf')] * (amount + 1)
    minimum_number_of_coins[0] = 0

    # Iterate through each coin value
    for coin in coins:

        # Iterate through each amount from 1 to the target amount
        for current_amount in range(1, amount + 1):

            # Check if the current coin can be used for the current amount
            if coin <= current_amount:

                # Update min coins needed using current coin
                minimum_number_of_coins[current_amount] = min(
                    minimum_number_of_coins[current_amount],
                    1 + minimum_number_of_coins[current_amount - coin]
                )

    # If no solution, return -1
    if minimum_number_of_coins[amount] == float('inf'):
        return -1
    else:
        return minimum_number_of_coins[amount]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(amount * coins) – The algorithm's time complexity is determined by the nested loops. The outer loop iterates from 0 up to the target amount. The inner loop iterates through each of the available coin denominations. Therefore, the total number of operations is proportional to the product of the target amount and the number of coin denominations. Thus the algorithm runs in O(amount * coins) time, where amount is the target amount and coins is the number of coin denominations.

Space Complexity

O(amount) – The algorithm creates a table to store the minimum number of coins needed for each amount from 0 up to the target amount. Let's denote the target amount as 'amount'. This table requires space proportional to the 'amount'. Therefore, the auxiliary space used by the algorithm is O(amount), as the table's size scales linearly with the target amount.

Edge Cases

Case	How to Handle
coins is null or empty	Return -1 if coins is null or empty, as no coins are available to make up the amount.
amount is 0	Return 0 if amount is 0, as no coins are needed.
coins contains a zero	The algorithm should still function correctly as zero values can contribute to the total amount; however, it may lead to inefficiencies and the algorithm will need to avoid division by zero.
coins contains negative values	Return an error or throw an exception if coins contains negative values, as negative coin denominations are not physically possible and can lead to infinite loops.
amount is negative	Return an error or throw an exception if amount is negative, as it is not possible to make up a negative amount.
No combination of coins can make up the amount	Return -1 if the dynamic programming table's final entry indicates that no solution was found.
Integer overflow when calculating the minimum number of coins	Use a sufficiently large integer type or check for overflow during calculations, returning a large value (e.g., Infinity in JavaScript, Integer.MAX_VALUE in Java) to represent an impossible solution during intermediate steps.
Large amount and many coin denominations	Consider optimizing the dynamic programming approach using techniques like memoization or iterative DP to avoid excessive recursion or memory usage.

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 `coins` array contain denominations of 0, or negative values?
What is the maximum possible value for `amount` and the number of coins in the `coins` array?
If there are multiple combinations of coins that result in the minimum number, is any one acceptable?
If `amount` is 0, should I return 0 or is that an invalid input?
Are duplicate coin denominations allowed in the `coins` array, and if so, how should they be handled?

Brute Force Solution

Approach

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

Start by trying to make the amount using only the largest coin.
See how many of those coins fit, and if it's exactly the target amount, we're done! That is one way to make change.
If it's more than the target, it doesn't work, so discard this attempt and try something different.
If it's less than the target, figure out how much is left, and then try all combinations of the other coins to make up the remaining amount. For example, maybe use the next largest coin. Maybe use two of them.
Keep trying different numbers of the largest coin combined with all possible numbers of the other coins.
Repeat the previous step by trying all combinations of second largest coin combined with all possible numbers of the other coins
Each time we find a combination of coins that equals the target amount, record the number of coins used in that combination.
Once we've tried absolutely every possible combination of every coin type, compare all the successful combinations we found.
Choose the combination that uses the fewest coins. That's the answer!

Code Implementation

def coin_change_brute_force(coins, amount):
    minimum_number_of_coins = float('inf')

    def find_minimum_coins(remaining_amount, current_coin_count):
        nonlocal minimum_number_of_coins

        if remaining_amount == 0:
            minimum_number_of_coins = min(minimum_number_of_coins, current_coin_count)
            return

        if remaining_amount < 0:
            return

        # Iterate through each coin denomination
        for coin in coins:

            # Recursively explore the solution space by subtracting the coin
            # from the remaining amount and incrementing the coin count
            find_minimum_coins(remaining_amount - coin, current_coin_count + 1)

    find_minimum_coins(amount, 0)

    # If no combination was found, return -1
    if minimum_number_of_coins == float('inf'):
        return -1

    return minimum_number_of_coins

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:

Create a table to store the minimum number of coins needed for each amount from zero up to the target amount.
Start with an amount of zero, which requires zero coins.
For each coin value we have, go through our table. If the coin is less than or equal to the current amount we're considering, we can potentially use it.
Figure out how many coins it would take to reach the current amount if we used this coin. This will equal to '1 plus the number of coins for the remaining amount if we use this coin'.
Store the minimum number of coins to reach that amount. We keep updating a spot until we find the very best solution.
Repeat this for all the available coins and all the amounts.
After considering all possibilities, the final value in the table, at the spot that represents the target amount, will be the minimum number of coins needed.

Code Implementation

def coin_change(coins, amount):
    minimum_number_of_coins = [float('inf')] * (amount + 1)
    minimum_number_of_coins[0] = 0

    # Iterate through each coin value
    for coin in coins:

        # Iterate through each amount from 1 to the target amount
        for current_amount in range(1, amount + 1):

            # Check if the current coin can be used for the current amount
            if coin <= current_amount:

                # Update min coins needed using current coin
                minimum_number_of_coins[current_amount] = min(
                    minimum_number_of_coins[current_amount],
                    1 + minimum_number_of_coins[current_amount - coin]
                )

    # If no solution, return -1
    if minimum_number_of_coins[amount] == float('inf'):
        return -1
    else:
        return minimum_number_of_coins[amount]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
coins is null or empty	Return -1 if coins is null or empty, as no coins are available to make up the amount.
amount is 0	Return 0 if amount is 0, as no coins are needed.
coins contains a zero	The algorithm should still function correctly as zero values can contribute to the total amount; however, it may lead to inefficiencies and the algorithm will need to avoid division by zero.
coins contains negative values	Return an error or throw an exception if coins contains negative values, as negative coin denominations are not physically possible and can lead to infinite loops.
amount is negative	Return an error or throw an exception if amount is negative, as it is not possible to make up a negative amount.
No combination of coins can make up the amount	Return -1 if the dynamic programming table's final entry indicates that no solution was found.
Integer overflow when calculating the minimum number of coins	Use a sufficiently large integer type or check for overflow during calculations, returning a large value (e.g., Infinity in JavaScript, Integer.MAX_VALUE in Java) to represent an impossible solution during intermediate steps.
Large amount and many coin denominations	Consider optimizing the dynamic programming approach using techniques like memoization or iterative DP to avoid excessive recursion or memory usage.