Coin Change

Mark as Completed

Lesson

Write a function to solve the coin change problem. You are given an array of coins with different denominations and a total amount of money. Your task is to compute the fewest number of coins required to make up the total amount of money. The function should return an array of the minimum number of coins required. If there is no combination of coins that can make up the total amount, return -1.

For example, if the input is coins = [1, 5, 10, 25]
and totalAmount = 44
, the function should return [1, 1, 1, 1, 10, 25]
.

Walkthrough

The coin change problem can be solved using dynamic programming. The idea is to build a solution from the solution to smaller subproblems. We can start by creating an array dp
of size totalAmount + 1
and initialize it with Infinity
except for dp[0]
, which should be 0. Then we can loop through the denominations and update dp[i]
for all i
between the denomination and totalAmount
.For each denomination, we check if it can be used to form the total amount. If it can be used, we update dp[i]
by taking the minimum of dp[i]
and dp[i - denomination] + 1
. This means that we either continue using the current denomination or we switch to a smaller denomination.After updating dp
for all denominations, we can reconstruct the solution by starting from dp[totalAmount]
and backtracking through the array. We can use the updated dp
array to keep track of the denominations used.

Here's the code:

function coinChange(coins, totalAmount) {
  const dp = new Array(totalAmount + 1).fill(Infinity);
  dp[0] = 0;

  for (const denomination of coins) {
    for (let i = denomination; i <= totalAmount; i++) {
      if (i - denomination >= 0) {
        dp[i] = Math.min(dp[i], dp[i - denomination] + 1);
      }
    }
  }

  if (dp[totalAmount] === Infinity) {
    return -1;
  }

  const result = [];
  let i = totalAmount;

  while (i > 0) {
    for (const denomination of coins) {
      if (i - denomination >= 0 && dp[i - denomination] === dp[i] - 1) {
        result.push(denomination);
        i -= denomination;
        break;
      }
    }
  }

  return result;
}

Big O Complexity Analysis: The time complexity of this solution is O(nm), where n is the total amount and m is the number of denominations. We iterate through each denomination for each possible total amount, so the time complexity is proportional to the product of n and m.

The space complexity of this solution is also O(nm) because we use a two-dimensional array dp
of size n x m.

Previous Lesson Next Lesson