Coin Change Minimum Coins in DSA Javascript - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount

↓

Initialize DP array with Infinity

↓

Set dp[0

↓

For each coin

↓

For each amount from coin to target

↓

Update dp[amount

↓

After all coins processed

↓

Check dp[target

Yes No↓

Return -1

We build a table dp where dp[x] is the minimum coins needed for amount x. We update dp by trying each coin for all amounts up to target.

Execution Sample

DSA Javascript

const coins = [1, 3, 4];
const amount = 6;
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (const coin of coins) {
  for (let x = coin; x <= amount; x++) {
    dp[x] = Math.min(dp[x], dp[x - coin] + 1);
  }
}
console.log(dp[amount] === Infinity ? -1 : dp[amount]);

Calculate minimum coins needed to make amount 6 using coins 1, 3, and 4.

Execution Table

Step	Operation	Amount Index (x)	Coin Used	dp Array State	Explanation
1	Initialize dp	-	-	[0, ∞, ∞, ∞, ∞, ∞, ∞]	dp[0] = 0, others set to Infinity
2	Use coin 1	1	1	[0, 1, ∞, ∞, ∞, ∞, ∞]	dp[1] = min(∞, dp[0]+1)=1
3	Use coin 1	2	1	[0, 1, 2, ∞, ∞, ∞, ∞]	dp[2] = min(∞, dp[1]+1)=2
4	Use coin 1	3	1	[0, 1, 2, 3, ∞, ∞, ∞]	dp[3] = min(∞, dp[2]+1)=3
5	Use coin 1	4	1	[0, 1, 2, 3, 4, ∞, ∞]	dp[4] = min(∞, dp[3]+1)=4
6	Use coin 1	5	1	[0, 1, 2, 3, 4, 5, ∞]	dp[5] = min(∞, dp[4]+1)=5
7	Use coin 1	6	1	[0, 1, 2, 3, 4, 5, 6]	dp[6] = min(∞, dp[5]+1)=6
8	Use coin 3	3	3	[0, 1, 2, 1, 4, 5, 6]	dp[3] = min(3, dp[0]+1)=1 (better)
9	Use coin 3	4	3	[0, 1, 2, 1, 2, 5, 6]	dp[4] = min(4, dp[1]+1)=2 (better)
10	Use coin 3	5	3	[0, 1, 2, 1, 2, 3, 6]	dp[5] = min(5, dp[2]+1)=3 (better)
11	Use coin 3	6	3	[0, 1, 2, 1, 2, 3, 2]	dp[6] = min(6, dp[3]+1)=2 (better)
12	Use coin 4	4	4	[0, 1, 2, 1, 1, 3, 2]	dp[4] = min(2, dp[0]+1)=1 (better)
13	Use coin 4	5	4	[0, 1, 2, 1, 1, 2, 2]	dp[5] = min(3, dp[1]+1)=2 (better)
14	Use coin 4	6	4	[0, 1, 2, 1, 1, 2, 2]	dp[6] = min(2, dp[2]+1)=2 (no change)
15	End	-	-	[0, 1, 2, 1, 1, 2, 2]	dp[6] = 2 means minimum 2 coins needed

💡 All coins processed, dp[6] = 2 is the minimum coins needed

Variable Tracker

Variable	Start	After coin 1	After coin 3	After coin 4	Final
dp	[0, ∞, ∞, ∞, ∞, ∞, ∞]	[0, 1, 2, 3, 4, 5, 6]	[0, 1, 2, 1, 2, 3, 2]	[0, 1, 2, 1, 1, 2, 2]	[0, 1, 2, 1, 1, 2, 2]
coin	-	1	3	4	4
x (amount index)	-	1 to 6	3 to 6	4 to 6	-

Key Moments - 3 Insights

Why do we initialize dp array with Infinity except dp[0]?

We use Infinity to represent amounts not yet reachable. dp[0] = 0 because zero coins are needed to make amount zero. See execution_table step 1.

Why do we update dp[x] with dp[x - coin] + 1?

Because if we can make amount (x - coin) with dp[x - coin] coins, adding one coin (current coin) makes amount x. This is shown in steps 2-14.

Why does dp[6] become 2 after using coin 3 and 4?

Because dp[6] can be made by dp[3] + 1 coin (coin 3) or dp[2] + 1 coin (coin 4). The minimum is 2 coins total. See steps 11 and 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the dp array state?

A [0, 1, 2, 3, 4, 5, 6]

B [0, 1, 2, 1, 4, 5, 6]

C [0, 1, 2, 1, 4, 5, 2]

D [0, 1, 2, 1, 2, 3, 2]

💡 Hint

Check the dp array state column in execution_table row with Step 8

At which step does dp[4] first get updated to 1?

A Step 5

B Step 9

C Step 12

D Step 14

💡 Hint

Look at the dp array state and explanation columns for dp[4] updates

If we remove coin 1 from coins, what happens to dp[1] after processing all coins?

A dp[1] remains Infinity

B dp[1] becomes 1

C dp[1] becomes 0

D dp[1] becomes 2

💡 Hint

Without coin 1, no coin can make amount 1, so dp[1] stays Infinity

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array where dp[x] = min coins for amount x
- Initialize dp with Infinity, dp[0] = 0
- For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1)
- Result is dp[amount], or -1 if Infinity
- Bottom-up dynamic programming approach

Full Transcript

This visualization shows how to find the minimum number of coins needed to make a target amount using given coin denominations. We create a dp array where each index represents an amount from 0 to the target. We start with dp[0] = 0 because zero coins are needed to make amount zero, and all other dp values are set to Infinity to indicate they are not yet reachable. We then iterate over each coin and for each amount from the coin value up to the target, we update dp[amount] to the minimum between its current value and dp[amount - coin] + 1, which means using one more coin of the current denomination. The execution table shows step-by-step how dp array values change as coins are processed. Finally, dp[target] gives the minimum coins needed or -1 if it remains Infinity. Key moments clarify why dp is initialized with Infinity, how updates happen, and why the final answer is correct. The quiz tests understanding of dp states at specific steps and the effect of removing coins.

Practice

1. What does the Coin Change Minimum Coins problem ask you to find?
Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount.

easy

A. Minimum number of coins needed to make the amount

B. Maximum number of coins that can be used

C. Total sum of all coin denominations

D. Number of different coin types available

Solution

1. Step 1: Understand the problem goal

   The problem asks for the fewest coins needed to reach a given amount using available coin denominations.

2. Step 2: Identify the correct interpretation

   Among the options, only the minimum number of coins needed matches the problem description.

3. Final Answer:

   Minimum number of coins needed to make the amount -> Option A

4. Quick Check:

   Minimum coins = problem goal [OK]

Hint: Focus on 'minimum coins' needed, not total or max coins [OK]

Common Mistakes:

• Confusing minimum with maximum coins
• Thinking about total sum of coins instead of count
• Ignoring the amount to be formed

2. Which of the following is the correct way to initialize the DP array for the Coin Change Minimum Coins problem in JavaScript?
const dp = new Array(amount + 1).fill(____);

easy

A. null

B. 0

C. -1

D. Infinity

Solution

1. Step 1: Understand DP array initialization

   We initialize dp array with Infinity to represent that initially no amount can be formed except 0.

2. Step 2: Confirm correct fill value

   Filling with Infinity helps us find minimum coins by comparing and updating values.

3. Final Answer:

   Infinity -> Option D

4. Quick Check:

   DP array filled with Infinity for min comparisons [OK]

Hint: Use Infinity to represent impossible amounts initially [OK]

Common Mistakes:

• Using 0 which implies amount can be formed with zero coins
• Using -1 which is not suitable for min comparisons
• Using null which causes errors in calculations

3. What will be the output of the following code?

const coins = [1, 2, 5];
const amount = 11;
function minCoins(coins, amount) {
  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(minCoins(coins, amount));

medium

A. 5

B. 4

C. 3

D. -1

Solution

1. Step 1: Trace DP array updates for amount 11

   Using coins 1, 2, 5, minimum coins for 11 are calculated as 3 (5+5+1) or 4 (5+2+2+2). The code finds 3 coins.

2. Step 2: Verify minimum coins count

   Actually, 11 = 5 + 5 + 1 uses 3 coins, which is minimum.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   11 = 5+5+1 = 3 coins [OK]

Hint: Check combinations starting with largest coin first [OK]

Common Mistakes:

• Counting coins incorrectly (e.g., 5 coins instead of 3)
• Returning -1 when solution exists
• Ignoring smaller coins in calculation

4. Find the error in the following code snippet for Coin Change Minimum Coins:

function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; 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];
}

medium

A. Loop should start from i = 1, not 0

B. dp array should be filled with 0 instead of Infinity

C. Return statement should return dp[0] instead of dp[amount]

D. coin <= i condition should be coin < i

Solution

1. Step 1: Analyze loop start index

   The outer loop starts at i = 0, but dp[0] is base case and should not be updated. Starting at 1 avoids unnecessary updates.

2. Step 2: Confirm correct loop range

   Starting from i = 1 ensures dp values build correctly from base case.

3. Final Answer:

   Loop should start from i = 1, not 0 -> Option A

4. Quick Check:

   Start loop at 1 to build dp correctly [OK]

Hint: Start dp loops from 1, not 0, to avoid base case overwrite [OK]

Common Mistakes:

• Starting loop at 0 causing incorrect dp updates
• Filling dp with 0 causing wrong min calculations
• Wrong return index causing wrong output

5. Given coins = [2, 3, 7] and amount = 13, what is the minimum number of coins needed to make the amount?
Use the Coin Change Minimum Coins approach.

hard

A. -1

B. 4

C. 5

D. 3

Solution

1. Step 1: Try combinations to form 13

   Using coins 7, 3, and 2, one way is 7 + 3 + 3 = 13 with 3 coins.

2. Step 2: Check if fewer coins possible

   No combination uses fewer than 4 coins to make 13 with these denominations.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   13 can be formed with 4 coins minimum [OK]

Hint: Try largest coin first, then fill remainder with smaller coins [OK]

Common Mistakes:

• Assuming no solution (-1) without checking combinations
• Counting coins incorrectly
• Ignoring coin reuse possibilities