A LeetCode Discussion: Coin Change Problems

Introduction

As a software engineer, preparing for interviews has become more important than ever in today’s uncertain tech landscape. Among dynamic programming challenges, the coin change problems are some of the trickiest to keep a solid grip on—they seem simple at first but are easy to forget. In this article, I’ll break down these problems in a way that helps others approach them with confidence, while also reinforcing my own understanding so the logic sticks more firmly the next time I encounter them.

The Coin Change I Problem

The coin change I problem asks the minimum number of coins to reach the requested amount.

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

While recursive solutions tend to be more intuitive, the tabulation method offers better readability - which is important to help readers understand.

The idea behind the solution is to keep track of the minimum number of coins to make up all the possible remainders up to the requested amount. Intuitively, when we understand that the objective is minimization, we can set a default value of minimum number of coins for each remainder as infinity. Using python, this is as simple as using the float('inf') number.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
      dp = [float('inf')] * (amount + 1)
      # ...

In the code snippet above, we can see we're initializing an array filled with the number infinity for all its members. The size of the array is intentionally set as amount + 1 to leave a space for the index 0 and leaving the rest of the indices idiomatic representation of the remainders. This means when we want to access the minimum number of coins for a given remainder, we can simply fetch them using the remainder number as their indices.

      # ...
      dp[0] = 0
      # [0, inf, inf, inf, ...]
      # ...

Next, we want to manually set the minimum number of coins to achieve 0 remainder as 0. This makes sense as the number of coins to achieve nothing is basically nothing. Hence, it is the first remainder in the array to achieve a non-infinity number.

      # ...
      for i in range(1, amount+1):
        for coin in coins:
          if coin > i:
            # skip if coin is larger than the remainder
            continue
          candidate_min_coins = 1 + dp[i - coin]
          # compare the previous minimum with candidate
          dp[i] = min(dp[i], candidate_min_coins)
      # ...

Moving on, we dive into the core of the solution. We can start to loop over and compute the minimum number of coins for all the possible remainders, from the smallest up until the requested amount. The logic behind the computation process involves:

1. checking for each coin whether the coin is applicable for the given remainder. This means, the coin cannot be greater than the remainder otherwise it won't make up the remainder at all.
2. revising the minimum number of coins for the given remainder if a smaller number of coins can make up the same amount. This step includes comparing the previous minimum number of coins and the new candidate.

      # ...
      if dp[amount] == float('inf'):
        return -1
      return dp[amount]

Ultimately, even the requested amount is treated as a remainder. For our solution to yield its answer, we can simply get the last member of the remainder minimum coins count array. However, there's still a chance that the requested amount cannot be constructed by any combination of the given coins. To handle this, we simply check whether the final answer is indeed anything smaller than infinity.

The following displays the full solution.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount+1):
            for coin in coins:
                if coin > i:
                  # skip if coin is larger than the remainder
                  continue
                candidate_min_coins = 1 + dp[i - coin]
                # compare the previous minimum with candidate
                dp[i] = min(dp[i], candidate_min_coins)

        if dp[-1] == float('inf'):
            return -1
        return dp[-1]

The Coin Change II Problem

The coin change II problem asks the number of ways to make up an amount using the given coins.

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.

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

Again, the idea behind the solution is to keep track of previous calculations. However, this time, we keep a record of the number of ways to make up all possible remainders. The number of ways to make up the smaller remainders determine the same for the larger ones.

We start the solution by initializing default values for the number of ways to make up all possible remainders. We want to collect the highest possible number of ways to make up an amount - this indicates the direction of the number change is upwards. Therefore, the default number of ways is zero - a minimum value.

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
      dp = [0] * (amount + 1)
      # [0,0,0,0,0,...]
      # ...

Then, we can initialize the number of ways to make up zero amount. There's only one way to make up the amount of zero.

      # ...
      dp[0] = 1
      # [1,0,0,0,0,...]
      # ...

Moving on, we want to iterate for every type of coin we have. For each coin, we want to assess for all possible remainder whether the coin can possibly make up each remainder. In the process, a remainder count that stays zero informs us that it cannot be made up. On the other hand, a remainder count that continuously increases by inheriting the smaller remainder counts shows that it is constructable.

for coin in coins:
    for i in range(1, amount + 1):
      dp[i] += dp[i - coin]

Lastly, we need to return the number of ways to construct the requested amount. To deliver this, we can simply get the count of the last element in the array.

The following shows the full solution.

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]

        return dp[amount]

Conclusion

• The coin change problems are dynamic programming problems with some special comparisons and operations that utilizes the previous computations.
• The coin change problems are more readable and easier to learn using the tabulation method.