Coin Change - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT_COIN = 'current_coin', CURRENT_COIN_COLOR = 'blue';
const CURRENT_AMOUNT = 'current_amount', CURRENT_AMOUNT_COLOR = 'orange';

function visMainFunction(inputCoins, amount) {
    initClassProperties();

    if (amount === 0) {
        notification(`✅ Since the target <b>amount</b> is <b>0</b>, no coins are needed. Returning <b>0</b>.`);
        return 0;
    }

    startBatch();
    const dp = new VisArray(amount + 1).fill(Infinity).options({ label: 'Minimum Coins needed (dp)' });
    dp[0] = 0; // Base case
    const coins = VisArray.from(inputCoins);
    endBatch();

    explanationAndColorSchemaNotifications();

    notification(`
      🔍 <b>Goal:</b> Find the <b>minimum number of coins</b> needed to make up amount <b>${amount}</b> using the given coins.<br/>
      📘 We'll use <b>Dynamic Programming (DP)</b>, where <code>dp[i]</code> stores the minimum number of coins needed to make amount <code>i</code>.
    `);

    notification(`
      🎯 <b>Initialization Complete:</b><br/>
      • Created a <b>DP table</b> of size <b>${amount + 1}</b>, initialized to <b>Infinity</b> (representing an unreachable amount).<br/>
      • <code>dp[0] = 0</code>, since <b>no coins</b> are needed to make amount <b>0</b>.<br/><br/>
      The goal is to fill in <code>dp[1..${amount}]</code> such that each entry represents the fewest coins needed for that amount.
    `);

    for (let coinIndex = 0; coinIndex < coins.length; coinIndex++) {
        const coin = coins[coinIndex];
        startPartialBatch();

        coins.makeVisManagerForIndex(coinIndex).addClass(CURRENT_COIN);

        notification(`
          🪙 <b>Processing Coin:</b> ${makeColoredSpan(coin, CURRENT_COIN_COLOR)}<br/>
          For each <b>target amount</b> <code>currentAmount</code> from <b>${coin}</b> to <b>${amount}</b>, 
          we check whether using this coin can reduce the number of coins needed to reach that amount.<br/><br/>
          
          💡 <i>Idea:</i> If we already know the minimum number of coins needed to make a smaller amount 
          <code>(currentAmount − coin(${makeColoredSpan(coin, CURRENT_COIN_COLOR)}))</code> 
          (using the coins encountered so far), we can form <code>currentAmount</code> 
          by adding one more coin of value ${makeColoredSpan(coin, CURRENT_COIN_COLOR)}.<br/>
          
          Since we traverse amounts in <b>increasing order</b> (from <code>${coin}</code> up to <code>${amount}</code>), 
          each smaller amount <code>(currentAmount − coin(${makeColoredSpan(coin, CURRENT_COIN_COLOR)}))</code> 
          has already been processed utilizing this coin. 
          This naturally allows <b>multiple uses of this coin (${makeColoredSpan(coin, CURRENT_COIN_COLOR)})</b>.
        `);

        for (let currentAmount = coin; currentAmount <= amount; currentAmount++) {
            const prevWays = dp[currentAmount - coin];
            const currentWays = dp[currentAmount];

            // Highlight current amount
            dp.makeVisManagerForIndex(currentAmount).addClass(CURRENT_AMOUNT);

            notification(`
              📌 <b>Updating dp[${makeColoredSpan(currentAmount, CURRENT_AMOUNT_COLOR)}]</b><br/>
              • Current value: <b>${currentWays}</b><br/>
              • If we include ${makeColoredSpan(coin, CURRENT_COIN_COLOR)}, we can form amount ${makeColoredSpan(currentAmount, CURRENT_AMOUNT_COLOR)} via 
                <code>dp[${currentAmount - coin}] + 1</code> = <b>${prevWays + 1}</b><br/>
              • <b>Taking minimum:</b> 
                <code>dp[${currentAmount}] = min(${currentWays}, ${prevWays + 1})</code><br/>
              → <b>Updated dp[${currentAmount}] = ${Math.min(currentWays, prevWays + 1)}</b>
            `);

            dp[currentAmount] = Math.min(currentWays, prevWays + 1);

            // Remove highlight for current amount after processing
            dp.makeVisManagerForIndex(currentAmount).removeClass(CURRENT_AMOUNT);
        }

        coins.makeVisManagerForIndex(coinIndex).removeClass(CURRENT_COIN);

        endBatch();
    }

    if (dp[amount] === Infinity) {
        notification(`❌ <b>Impossible:</b> Cannot make amount <b>${amount}</b> with given coins. Returning <b>-1</b>.`);
        return -1;
    }

    notification(`
      🏁 <b>Finished!</b><br/>
      The minimum number of coins needed to make amount <b>${amount}</b> is <b>${dp[amount]}</b>.<br/>
      📌 This final value is held in <code>dp[${amount}]</code>, representing the optimal (fewest) number of coins needed for the target amount.
    `);

    return dp[amount];
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();

  notification(`
    🎨 <b>Color Palette &amp; Legend</b><br/>
    • ${makeColoredSpan('coin (current)', CURRENT_COIN_COLOR)} — the coin value being processed in the <i>outer</i> loop.<br/>
    • ${makeColoredSpan('currentAmount', CURRENT_AMOUNT_COLOR)} — the DP index currently being updated in the <i>inner</i> loop.<br/>
  `);
}

function initClassProperties() {
    setClassProperties(CURRENT_COIN, { backgroundColor: CURRENT_COIN_COLOR });
    setClassProperties(CURRENT_AMOUNT, { backgroundColor: CURRENT_AMOUNT_COLOR });
}

Approach

Problem

Given coin denominations coins and a target amount, find the minimum number of coins needed to make up the amount. If it’s impossible, return -1.

DP Definition & Initialization

We’ll use a Dynamic Programming (DP) array where dp[i] stores the minimum number of coins needed to make amount i.

Initialize dp with size amount + 1, filling it with Infinity to represent amounts that are initially unreachable.
Set the base case: dp[0] = 0, since no coins are needed to make amount 0.

Transition & Loop Structure

For each coin coin in coins (outer loop):
- For each target amount currentAmount from coin up to amount (inclusive), check whether using this coin can reduce the number of coins needed for currentAmount.
- 💡 Idea: If the smaller amount (currentAmount − coin) is reachable using the coins encountered so far, then we can form currentAmount by adding one more coin. Formally:
  dp[currentAmount] = min(dp[currentAmount], dp[currentAmount − coin] + 1)
- Because we traverse currentAmount in increasing order (from coin to amount), the sub-amount (currentAmount − coin) has already been processed utilizing the current coin. This naturally allows multiple uses of this coin - for example, with coin = 5, dp[11] can build upon dp[6], which was already processed utilizing this same coin (5), effectively adding another 5 to reach 11..

Result

If dp[amount] === Infinity, it’s impossible → return -1.
Otherwise, return dp[amount] — the fewest coins needed to reach the target.

Time Complexity

O(n × amount) — where n is the number of available coins.

The algorithm iterates once for each coin, scanning all possible currentAmount values from coin up to amount. Therefore, the total number of iterations is proportional to n × amount.

Space Complexity

O(amount) — only the DP table is stored.

We maintain a one-dimensional DP array dp of size amount + 1, where each entry dp[i] stores the fewest coins needed to make amount i.

Input-1

Coin Change - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Problem

DP Definition & Initialization

Transition & Loop Structure

Result

Time Complexity

Space Complexity