Coin Change Minimum Coins in DSA Typescript

Mental Model

We want to find the smallest number of coins needed to make a certain amount using given coin values. We try all possibilities and remember the best results to avoid repeating work.

Analogy: Imagine you have different sized boxes and want to pack a gift with the fewest boxes possible. You try using the biggest boxes first, then smaller ones, and keep track of the best way to pack each size.

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

DP array (index = amount):
[0] [1] [2] [3] [4] [5] [6]
 ↑   ↑   ↑   ↑   ↑   ↑   ↑
 0   ?   ?   ?   ?   ?   ?

Dry Run Walkthrough

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

Goal: Find the minimum number of coins needed to make amount 6

Step 1: Initialize dp array with dp[0] = 0 and others as infinity (unknown)

dp: [0, ∞, ∞, ∞, ∞, ∞, ∞]

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

Step 2: Calculate dp[1]: try coin 1 -> dp[1] = dp[0] + 1 = 1

dp: [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: Only coin 1 fits amount 1, so 1 coin needed

Step 3: Calculate dp[2]: try coin 1 -> dp[2] = dp[1] + 1 = 2

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

Why: Only coin 1 fits amount 2, so 2 coins needed

Step 4: Calculate dp[3]: try coin 1 -> dp[3] = dp[2] + 1 = 3; try coin 3 -> dp[3] = dp[0] + 1 = 1 (better)

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

Why: Using coin 3 alone is better than three 1 coins

Step 5: Calculate dp[4]: try coin 1 -> dp[4] = dp[3] + 1 = 2; try coin 3 -> dp[4] = dp[1] + 1 = 2; try coin 4 -> dp[4] = dp[0] + 1 = 1 (best)

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

Why: Coin 4 alone is best for amount 4

Step 6: Calculate dp[5]: try coin 1 -> dp[5] = dp[4] + 1 = 2; try coin 3 -> dp[5] = dp[2] + 1 = 3; try coin 4 -> dp[5] = dp[1] + 1 = 2

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

Why: Minimum coins for 5 is 2 (e.g., 1+4)

Step 7: Calculate dp[6]: try coin 1 -> dp[6] = dp[5] + 1 = 3; try coin 3 -> dp[6] = dp[3] + 1 = 2 (better); try coin 4 -> dp[6] = dp[2] + 1 = 3

dp: [0, 1, 2, 1, 1, 2, 2]

Why: Using coin 3 twice is best for amount 6

Result:

dp: [0, 1, 2, 1, 1, 2, 2]
Minimum coins needed: 2

Annotated Code

DSA Typescript

class CoinChange {
  static minCoins(coins: number[], amount: number): number {
    const dp: number[] = Array(amount + 1).fill(Infinity);
    dp[0] = 0; // base case: 0 coins to make 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]; // if no solution, return -1
  }
}

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

dp[0] = 0; // base case: 0 coins to make amount 0

initialize base case for dp

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

iterate over all amounts from 1 to target

for (const coin of coins) {

try 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 combination found

Output

2

Complexity Analysis

Time: O(n * amount) because we compute dp for each amount and try all n coins

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

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

Edge Cases

amount = 0

returns 0 since no coins are needed

DSA Typescript

dp[0] = 0; // base case: 0 coins to make amount 0

coins array empty

returns -1 since no coins available to make any amount

DSA Typescript

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

amount cannot be formed by given coins

returns -1 indicating no solution

DSA Typescript

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 dynamic programming with a dp array to build solutions from smaller amounts up to the target.

Common Mistakes

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

Mistake: Not checking if coin value is less than or equal to current amount before accessing dp[i - coin]
Fix: Add condition if (coin <= i) before updating dp[i]

Mistake: Returning dp[amount] directly without checking if it is Infinity
Fix: Return -1 if dp[amount] is Infinity to indicate no solution

Summary

Finds the minimum number of coins needed to make a target amount from given coin denominations.

Use when you want the least number of items to sum up to a value from a set of options.

Build the solution bottom-up by solving smaller amounts first and using those results to solve bigger amounts.

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