Solving Coin Change Problem in JavaScript: Step-by-Step Guide

The Coin Change Problem is one of the most classic algorithmic challenges you will encounter in computer science and software engineering interviews. At its core, the problem asks you to determine the minimum number of coins required to make up a given amount, using a set of coin denominations. While the problem statement sounds simple, the underlying solution introduces you to powerful concepts like dynamic programming, memoization, and greedy algorithms. In this tutorial, we will walk through the problem from first principles, build a working JavaScript solution, and discuss best practices for writing clean, efficient code.

What Is the Coin Change Problem?

Imagine you are given a set of coin denominations, such as [1, 5, 10, 25], and a target amount, such as 36. Your goal is to find the fewest number of coins that add up to that amount. In this example, the optimal answer would be 3 coins: one 25-cent coin, one 10-cent coin, and one 1-cent coin. If it is impossible to form the amount with the given coins, the function should return -1.

There are two common variations of the problem. The first asks for the minimum number of coins, and the second asks for the total number of combinations that can form the amount. In this tutorial, we focus on the first variation, which is the more frequently asked version in interviews.

Why the Coin Change Problem Matters

The Coin Change Problem is more than just an academic exercise. It models real-world scenarios such as currency exchange systems, vending machine logic, and resource allocation problems. More importantly, it serves as an excellent gateway into dynamic programming, a technique used to solve problems by breaking them down into overlapping subproblems and storing intermediate results to avoid redundant computation.

Understanding this problem trains you to recognize when a naive recursive solution can be optimized, how to identify overlapping subproblems, and how to trade memory for speed. These are foundational skills for any developer working on performance-sensitive applications.

The Naive Recursive Approach

Before jumping to the optimal solution, it helps to understand the brute-force approach. The idea is simple: for each coin, subtract its value from the target amount and recursively solve the smaller problem. The base case is when the amount reaches zero, meaning we have successfully formed the amount.

function coinChangeNaive(coins, amount) {
  if (amount === 0) return 0;
  if (amount < 0) return -1;

  let minCoins = Infinity;

  for (const coin of coins) {
    const result = coinChangeNaive(coins, amount - coin);
    if (result !== -1) {
      minCoins = Math.min(minCoins, result + 1);
    }
  }

  return minCoins === Infinity ? -1 : minCoins;
}

console.log(coinChangeNaive([1, 5, 10, 25], 36)); // 3

While this solution works, it has a major flaw: it recomputes the same subproblems repeatedly. For larger amounts, the number of recursive calls grows exponentially, making this approach impractical. This is where dynamic programming comes to the rescue.

The Dynamic Programming Solution

Dynamic programming solves the inefficiency of the naive approach by storing the results of subproblems in an array. We create an array called dp where dp[i] represents the minimum number of coins needed to make amount i. We initialize every value to a large number (representing "impossible" so far), except for dp[0], which is zero because zero coins are needed to make zero amount.

Then, for each amount from 1 to the target, we try every coin. If the coin value is less than or equal to the current amount, we check whether using that coin leads to a smaller number of coins than what we currently have stored.

function coinChange(coins, amount) {
  // Create a dp array filled with a value larger than any possible answer
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

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

  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 10, 25], 36)); // 3
console.log(coinChange([2], 3));             // -1
console.log(coinChange([1], 0));             // 0

Let us break down how this works. When i = 6 and our coins are [1, 5, 10, 25], we check each coin. For coin 1, we look at dp[5] and add one. For coin 5, we look at dp[1] and add one. The minimum of these options becomes dp[6]. By the time we finish iterating, dp[amount] holds the optimal answer.

Time and Space Complexity

The time complexity of the dynamic programming solution is O(amount * coins.length) because we iterate through every amount and, for each amount, through every coin. The space complexity is O(amount) because we store an array of size amount + 1.

Compared to the exponential time complexity of the naive recursive approach, this is a massive improvement. For most practical inputs, this solution runs efficiently and is the standard answer expected in coding interviews.

Top-Down Approach with Memoization

Dynamic programming can be implemented in two styles: bottom-up (which we just covered) and top-down with memoization. The top-down approach starts from the original problem and recursively breaks it down, but caches results to avoid recomputation. Some developers find this style more intuitive because it mirrors the natural recursive thought process.

function coinChangeMemo(coins, amount) {
  const memo = new Map();

  function helper(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return -1;
    if (memo.has(remaining)) return memo.get(remaining);

    let minCoins = Infinity;

    for (const coin of coins) {
      const result = helper(remaining - coin);
      if (result !== -1) {
        minCoins = Math.min(minCoins, result + 1);
      }
    }

    const answer = minCoins === Infinity ? -1 : minCoins;
    memo.set(remaining, answer);
    return answer;
  }

  return helper(amount);
}

console.log(coinChangeMemo([1, 5, 10, 25], 36)); // 3

Both approaches have the same asymptotic complexity, but the bottom-up approach typically has lower constant factors because it avoids the overhead of recursive function calls. However, the top-down approach only computes the subproblems that are actually needed, which can be advantageous in certain scenarios.

When the Greedy Approach Fails

A common temptation is to solve the problem greedily by always picking the largest coin possible. While this works for standard US coin denominations, it fails for arbitrary sets. Consider coins [1, 3, 4] and amount 6. The greedy approach would pick 4 first, leaving 2, which requires two 1-cent coins, for a total of three coins. The optimal solution is two 3-cent coins.

// Greedy approach - works for some cases but not all
function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a); // Sort descending
  let count = 0;
  let remaining = amount;

  for (const coin of coins) {
    while (remaining >= coin) {
      remaining -= coin;
      count++;
    }
  }

  return remaining === 0 ? count : -1;
}

console.log(coinChangeGreedy([1, 3, 4], 6)); // 3 (incorrect, optimal is 2)

This example illustrates why dynamic programming is necessary. The greedy approach makes locally optimal choices that may not lead to a globally optimal solution. Always validate whether a greedy strategy is provably correct for your specific coin set before using it.

Best Practices

Validate inputs: Always check for edge cases such as an empty coins array, a negative amount, or an amount of zero. Returning early for these cases improves both correctness and performance.
Choose the right initialization value: Using Infinity as the initial value in the dp array clearly signals "not yet computed" and avoids off-by-one errors that can occur when using amount + 1.
Prefer bottom-up for predictable performance: Unless you have a specific reason to use memoization, the bottom-up approach tends to be faster in JavaScript due to the overhead of recursive calls and potential stack limits.
Sort coins when helpful: Sorting coins in descending order can allow early termination in some optimized variants, though it does not change the worst-case complexity.
Write tests: Cover cases including zero amount, impossible amounts, single-coin arrays, and large amounts to ensure your solution is robust.
Consider space optimization: If memory is a concern, analyze whether you can reduce the dp array or use alternative data structures, though for this problem the linear space is usually acceptable.

Testing Your Solution

A robust solution should be tested against a variety of inputs. Here is a simple test suite you can use to verify your implementation:

function runTests() {
  const tests = [
    { coins: [1, 5, 10, 25], amount: 36, expected: 3 },
    { coins: [2], amount: 3, expected: -1 },
    { coins: [1], amount: 0, expected: 0 },
    { coins: [1, 3, 4], amount: 6, expected: 2 },
    { coins: [186, 419, 83, 408], amount: 6249, expected: 20 },
    { coins: [1, 2, 5], amount: 11, expected: 3 },
  ];

  for (const { coins, amount, expected } of tests) {
    const result = coinChange(coins, amount);
    const status = result === expected ? "PASS" : "FAIL";
    console.log(`${status}: coins=[${coins}], amount=${amount}, got=${result}, expected=${expected}`);
  }
}

runTests();

Running these tests will confirm that your dynamic programming solution handles standard cases, edge cases, and larger inputs correctly. If any test fails, revisit your loop logic and initialization values.

Conclusion

The Coin Change Problem is a foundational exercise that teaches you how to transform an inefficient recursive solution into an optimized dynamic programming solution. By understanding both the bottom-up and top-down approaches, recognizing the limitations of greedy algorithms, and following best practices for input validation and testing, you will be well-equipped to tackle this problem and similar dynamic programming challenges in real-world applications and technical interviews. Mastering this pattern opens the door to solving a wide range of optimization problems with confidence and clarity.