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.