Coin Change Minimum Coins in DSA Javascript

Mental Model

Find the smallest number of coins needed to make a target amount using given coin values. We build up solutions from smaller amounts to the target.

Analogy: Imagine you want to pay a certain amount using coins from your pocket. You try to use the fewest coins possible by checking all smaller amounts first and remembering the best way to pay them.

coins = [1, 3, 4]
amount = 6

We create an array dp where dp[i] means minimum coins to make amount i:

Index: 0  1  2  3  4  5  6
Value: 0  ?  ?  ?  ?  ?  ?

We fill dp from left to right using coins.

Dry Run Walkthrough

Input: coins = [1, 3, 4], amount = 6

Goal: Find minimum coins needed to make amount 6

Step 1: Initialize dp array with dp[0] = 0 and others as Infinity

dp = [0, ∞, ∞, ∞, ∞, ∞, ∞]

Why: 0 coins needed to make amount 0; others unknown yet

Step 2: Calculate dp[1]: check coins 1,3,4; only coin 1 fits

dp = [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: Using coin 1, dp[1] = dp[0] + 1 = 1

Step 3: Calculate dp[2]: check coins 1,3,4; only coin 1 fits

dp = [0, 1, 2, ∞, ∞, ∞, ∞]

Why: Using coin 1, dp[2] = dp[1] + 1 = 2

Step 4: Calculate dp[3]: check coins 1,3,4; coins 1 and 3 fit

dp = [0, 1, 2, 1, ∞, ∞, ∞]

Why: Using coin 3, dp[3] = dp[0] + 1 = 1 (better than dp[2]+1=3)

Step 5: Calculate dp[4]: check coins 1,3,4; all fit

dp = [0, 1, 2, 1, 1, ∞, ∞]

Why: Using coin 4, dp[4] = dp[0] + 1 = 1 (best)

Step 6: Calculate dp[5]: check coins 1,3,4; all fit

dp = [0, 1, 2, 1, 1, 2, ∞]

Why: Using coin 1, dp[5] = dp[4] + 1 = 2 (better than dp[2]+1=3 or dp[1]+1=2)

Step 7: Calculate dp[6]: check coins 1,3,4; all fit

dp = [0, 1, 2, 1, 1, 2, 2]

Why: Using coin 3, dp[6] = dp[3] + 1 = 2 (best)

Result:

dp = [0, 1, 2, 1, 1, 2, 2]
Minimum coins to make 6 = 2

Annotated Code

DSA Javascript

class CoinChange {
  static minCoins(coins, amount) {
    const dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0; // 0 coins needed for amount 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); // update dp[i] if using coin reduces count
        }
      }
    }

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

// Driver code
const coins = [1, 3, 4];
const amount = 6;
const result = CoinChange.minCoins(coins, amount);
console.log(result);

dp[0] = 0; // 0 coins needed for amount 0

Initialize base case

for (let i = 1; i <= amount; i++) {

Iterate over all amounts from 1 to target

for (const coin of coins) {

Check each coin for current amount

if (coin <= i) {

Only consider coins not larger than current amount

dp[i] = Math.min(dp[i], dp[i - coin] + 1);

Update dp[i] with minimum coins using this coin

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

Return result or -1 if no solution

Output

2

Complexity Analysis

Time: O(n * amount) because we compute dp for each amount up to target and check all n coins each time

Space: O(amount) because we store minimum coins needed for all amounts up to target

vs Alternative: Compared to recursive brute force which is exponential, this dynamic programming approach is efficient and avoids repeated work

Edge Cases

amount = 0

Returns 0 because no coins are needed

DSA Javascript

dp[0] = 0; // 0 coins needed for amount 0

coins array empty

Returns -1 because no coins to use

DSA Javascript

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

amount cannot be formed by given coins

Returns -1 indicating no solution

DSA Javascript

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

When to Use This Pattern

When asked to find the minimum number of items to reach a target sum using given options, use the Coin Change Minimum Coins pattern with dynamic programming to build solutions from smaller sums.

Common Mistakes

Mistake: Not initializing dp[0] to 0, causing incorrect base case
Fix: Set dp[0] = 0 before starting the loops

Mistake: Using a greedy approach that picks largest coin first, which fails for some inputs
Fix: Use dynamic programming to consider all coins for each amount

Mistake: Not checking if coin <= current amount before accessing dp[i - coin]
Fix: Add condition if (coin <= i) before updating dp[i]

Summary

Finds the fewest coins needed to make a target amount from given coin values.

Use when you need the minimum number of coins or items to sum up to a value.

Build solutions from smaller amounts up to the target, remembering best results.

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