< Back




322. Coin Change

We're given an array of coin values and we're asked to find the minimum number of coins that we can
combine to create a target amount. We can use each coin an infinite number of times.

We use dynamic programming and memoization to solve this problem efficiently. We create a table of
size amount + 1, and initialize this table with float('inf') values. We set the 0th index to 0. This
table represents the minimum number of coins required to create the amount at index i - that we know
so far. This table is continuously updated as we iterate through the coins and find new solutions.

For each coin, we'll iterate through the amounts from coin -> amount + 1. At each step of the
iteration, we evaluate the minimum number of coins required to create the amount at index i. We keep
the minimum of the current value at index i or the value at index T[i - coin] + 1.

Essentially, if it takes less coins to create the value with the current coin we're inspecting versus
the value we've calculated so far, we update the value at index i. Eventually, we've calculated the
minimum number of coins required to create the target amount.

The solution is as follows:


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

          for coin in coins:
              for value in range(coin, amount + 1):
                  T[value] = min(T[value], T[value - coin] + 1)

          return T[amount] if T[amount] != float("inf") else -1


_ Time Complexity:

  O(n * k) - Where n is the number of coins, and k is the amount.

_ Space Complexity:

  O(k) - We maintain a table of length k to memoize our answers.