Coin Change Minimum Coins in DSA Typescript - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount

↓

Initialize DP array with large values

↓

Set dp[0

↓

For each coin

↓

For each amount from coin to target

↓

Update dp[amount

↓

After filling dp array

↓

If dp[target

↓

End

We build a table dp where dp[i] stores the minimum coins needed for amount i. We update dp by trying each coin for all amounts.

Execution Sample

DSA Typescript

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);
  }
}

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

Execution Table

Step	Operation	Amount Index (x)	Coin Used	dp[x] Before	dp[x - coin]	dp[x] After	dp Array State
1	Initialize dp	-	-	-	-	0	[0, ∞, ∞, ∞, ∞, ∞, ∞]
2	Use coin 1	1	1	∞	dp[0]=0	1	[0, 1, ∞, ∞, ∞, ∞, ∞]
3	Use coin 1	2	1	∞	dp[1]=1	2	[0, 1, 2, ∞, ∞, ∞, ∞]
4	Use coin 1	3	1	∞	dp[2]=2	3	[0, 1, 2, 3, ∞, ∞, ∞]
5	Use coin 1	4	1	∞	dp[3]=3	4	[0, 1, 2, 3, 4, ∞, ∞]
6	Use coin 1	5	1	∞	dp[4]=4	5	[0, 1, 2, 3, 4, 5, ∞]
7	Use coin 1	6	1	∞	dp[5]=5	6	[0, 1, 2, 3, 4, 5, 6]
8	Use coin 3	3	3	3	dp[0]=0	1	[0, 1, 2, 1, 4, 5, 6]
9	Use coin 3	4	3	4	dp[1]=1	2	[0, 1, 2, 1, 2, 5, 6]
10	Use coin 3	5	3	5	dp[2]=2	3	[0, 1, 2, 1, 2, 3, 6]
11	Use coin 3	6	3	6	dp[3]=1	2	[0, 1, 2, 1, 2, 3, 2]
12	Use coin 4	4	4	2	dp[0]=0	1	[0, 1, 2, 1, 1, 3, 2]
13	Use coin 4	5	4	3	dp[1]=1	2	[0, 1, 2, 1, 1, 2, 2]
14	Use coin 4	6	4	2	dp[2]=2	2	[0, 1, 2, 1, 1, 2, 2]
15	End	-	-	-	-	-	[0, 1, 2, 1, 1, 2, 2]

💡 Finished all coins and amounts; dp[6] = 2 means minimum 2 coins needed.

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 12	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	-
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 means zero coins needed for amount zero. See execution_table row 1 where dp is initialized.

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 of current coin value makes amount x. This is shown in rows 2-14 where dp[x] updates based on dp[x - coin].

Why does dp[6] end up as 2 and not a larger number?

Because using coins 3 and 3 or 4 and 2 coins, minimum coins to make 6 is 2. The dp array updates to smaller values as better combinations are found, shown in rows 11, 14, and final dp state.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is dp[3] after using coin 3?

A 3

B 1

C ∞

D 0

💡 Hint

Check the 'dp[x] After' column at step 8 for amount index 3.

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

A Step 12

B Step 9

C Step 5

D Step 14

💡 Hint

Look at dp array state changes in steps 9 and 12 for dp[4].

If coin 2 was added, how would dp[6] change compared to final dp?

A dp[6] would remain 2

B dp[6] would increase

C dp[6] would decrease

D dp[6] would become Infinity

💡 Hint

Adding coin 2 gives more ways to form 6 with fewer coins, so dp[6] could decrease.

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array of size amount+1, fill with Infinity
- dp[0] = 0 (0 coins for amount 0)
- For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1)
- dp[amount] gives minimum coins or Infinity if no solution
- 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 for amount zero, and all other dp values are set to Infinity to indicate unreachable amounts. Then, for each coin, we update the dp array for amounts from the coin's value up to the target. We check if using the coin reduces the number of coins needed for that amount by comparing dp[x] with dp[x - coin] + 1. After processing all coins, dp[amount] holds the minimum coins needed or Infinity if no combination is possible. The execution table traces each update step, showing how dp values improve over time. Key moments clarify why initialization uses Infinity, how updates work, and why the final dp value represents the answer. The quiz tests understanding of dp updates and effects of adding coins.

Practice

1. What does the "Coin Change Minimum Coins" problem ask you to find?

easy

A. The maximum amount of money you can make with given coins

B. The total number of different coins available

C. The least number of coins needed to make a given amount

D. The sum of all coin values

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of coins needed to make a specific amount.

2. Step 2: Differentiate from other coin problems

   It is not about counting coins or maximum amount, but minimizing coin count for exact amount.

3. Final Answer:

   The least number of coins needed to make a given amount -> Option C

4. Quick Check:

   Minimum coins = least number needed [OK]

Hint: Focus on minimum coins to form amount, not total coins [OK]

Common Mistakes:

• Confusing minimum coins with total coin types
• Thinking problem asks for maximum amount
• Ignoring the exact amount requirement

2. Which of the following is the correct TypeScript function signature for a coin change minimum coins function?

easy

A. function minCoins(coins: number[], amount: number): number

B. function minCoins(amount: number, coins: number[]): void

C. function minCoins(coins: number, amount: number[]): number[]

D. function minCoins(coins: string[], amount: string): number

Solution

1. Step 1: Check parameter types and order

   The function should take an array of coin values (number[]) and an amount (number).

2. Step 2: Check return type

   The function returns a number representing minimum coins needed.

3. Final Answer:

   function minCoins(coins: number[], amount: number): number -> Option A

4. Quick Check:

   Correct types and return number [OK]

Hint: Coins array first, amount second, returns number [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong types like string instead of number
• Returning void or array instead of number

3. What is the output of the following TypeScript code?

function minCoins(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(amount + 1);
  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] > amount ? -1 : dp[amount];
}

console.log(minCoins([1, 2, 5], 11));

medium

A. 2

B. 3

C. -1

D. 5

Solution

1. Step 1: Understand dp array initialization

   dp array size is 12 (0 to 11), initialized with 12 (amount+1), dp[0] = 0.

2. Step 2: Calculate dp values for amount 11

   Using coins 1,2,5, minimum coins for 11 is 3 (5+5+1).

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Minimum coins for 11 with [1,2,5] = 3 [OK]

Hint: Use dp array to track min coins for each amount [OK]

Common Mistakes:

• Returning dp[amount] without checking if > amount
• Misunderstanding dp initialization
• Confusing coin values and indices

4. Identify the bug in this TypeScript code for minimum coins:

function minCoins(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    dp[i] = Infinity;
    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. The condition should be coin <= i, not coin < i

B. dp array should be initialized with Infinity, not 0

C. dp[0] should be Infinity, not 0

D. Return statement should check dp[amount] > Infinity

Solution

1. Step 1: Check coin usage condition

   The condition 'coin < i' skips cases where coin equals i, missing exact matches.

2. Step 2: Correct condition to include equal coins

   Change condition to 'coin <= i' to allow using coin equal to current amount.

3. Final Answer:

   The condition should be coin <= i, not coin < i -> Option A

4. Quick Check:

   Include coin equal to amount [OK]

Hint: Use <= to include exact coin matches [OK]

Common Mistakes:

• Using < instead of <= in coin check
• Initializing dp array incorrectly
• Wrong return condition check

5. Given coins = [2, 3, 7] and amount = 13, what is the minimum number of coins needed? Use the coin change minimum coins approach.

hard

A. -1

B. 4

C. 2

D. 3

Solution

1. Step 1: Try combinations to form 13

   Possible combos: 7+3+3 = 3 coins, 2+2+2+7 = 4 coins, etc.

2. Step 2: Identify minimum coins

   Minimum coins is 3 using 7, 3, and 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   7+3+3 = 13 with 3 coins [OK]

Hint: Try largest coins first to minimize count [OK]

Common Mistakes:

• Assuming no solution (-1) without checking combos
• Counting coins incorrectly
• Ignoring combinations with repeated coins