Coding Interview Questions | Coin Change

January 15th, 2024

Coin Change Problem Introduction:

This summary will talk about my solution to the coin change problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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.

How do you solve the Coin Change Problem using Dynamic Programming?

Solution:

function coinChange(coins: number[], amount: number): number {
  if (amount === 0) {
    return 0;
  }
  const amounts = Array.from({ length: amount }, () => -1);

  for (
    let currentAmountIdx = 0;
    currentAmountIdx < amounts.length;
    currentAmountIdx++
  ) {
    const currentAmount = currentAmountIdx + 1;

    for (const coin of coins) {
      if (coin === currentAmount) {
        amounts[currentAmountIdx] = 1;
        break;
      }

      //Amount can be created with this coin if
      //the amount could be created at the index of the currentAmount - coin
      const canCreateAmount =
        currentAmount - coin - 1 >= 0 &&
        amounts[currentAmount - coin - 1] !== -1;

      if (canCreateAmount) {
        const currentAmountCoins = amounts[currentAmountIdx - coin] + 1;
        if (amounts[currentAmountIdx] === -1) {
          amounts[currentAmountIdx] = currentAmountCoins;
        } else {
          amounts[currentAmountIdx] = Math.min(
            amounts[currentAmountIdx],
            currentAmountCoins
          );
        }
      }
    }
  }

  return amounts[amount - 1];
}

Coin Change Solution Summary:

Below is a breakdown of the key aspects of the solution above for the coin change problem:

1. Base Case Handling: The algorithm first checks if the amount is 0, returning 0 as the fewest number of coins needed in this case.

2. Dynamic Programming Array: Next, we initialize an array amounts of length equal to the amount, representing the fewest number of coins needed for each amount. It sets initial values to -1.

3. Iterative Coin Calculation: We then iterate through the amounts array, calculating the fewest coins needed for each amount by considering all available coin denominations.

4. Coin Comparison and Update: For each coin denomination, the algorithm checks if the amount can be created with this coin. If so, it updates the amounts array with the minimum number of coins needed.

5. Final Result: Finally, the result is obtained from the last element of the amounts array, representing the fewest coins needed to make up the total amount.

Complexities

1. Time Complexity: The time complexity of the solution is determined by the nested iteration through the amounts array and the coins. It is influenced by the product of the length of amounts and the number of coins, denoted as O(n * m), where n is the amount and m is the number of coins.

2. Space Complexity: The space complexity is O(n) as the algorithm uses an array of size amount to store the fewest number of coins needed for each amount.