Coin Change Total Number of Ways in DSA Typescript - Time & Space Complexity

Time Complexity: Coin Change Total Number of Ways

O(m * n)

Understanding Time Complexity

We want to understand how the time needed to find the total ways to make change grows as we add more coins or increase the amount.

How does the number of steps change when the input size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countWays(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let x = coin; x <= amount; x++) {
      dp[x] += dp[x - coin];
    }
  }
  return dp[amount];
}
    

This code calculates how many ways we can make the given amount using the coins available.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each coin, we loop through amounts from coin value up to the target amount.
• How many times: Outer loop runs once per coin (m times), inner loop runs up to amount (n times).

How Execution Grows With Input

As we add more coins or increase the amount, the steps increase by multiplying these two factors.

Input Size (coins m, amount n)	Approx. Operations
m=5, n=10	~50
m=5, n=100	~500
m=10, n=1000	~10,000

Pattern observation: Doubling coins or amount roughly doubles or multiplies the total steps, showing a combined growth.

Final Time Complexity

Time Complexity: O(m * n)

This means the time grows proportionally to the number of coins times the amount we want to make.

Common Mistake

[X] Wrong: "The time depends only on the amount, not the number of coins."

[OK] Correct: Each coin adds a full loop over the amounts, so more coins mean more work.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves efficiency and prepares you to discuss trade-offs in similar problems.

Self-Check

"What if we used recursion with memoization instead of this bottom-up approach? How would the time complexity change?"

Practice

1. What does the "Coin Change Total Number of Ways" problem ask you to find?

easy

A. The total number of ways to make a target amount using given coin denominations.

B. The minimum number of coins needed to make a target amount.

C. The maximum value of coins that can be used to reach the target.

D. The total sum of all coin denominations.

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible ways to make a target amount using given coins.

2. Step 2: Differentiate from similar problems

   Unlike minimum coins problem, this counts combinations, not minimum count.

3. Final Answer:

   The total number of ways to make a target amount using given coin denominations. -> Option A

4. Quick Check:

   Counting ways = total combinations [OK]

Hint: Count combinations, not minimum coins needed [OK]

Common Mistakes:

• Confusing with minimum coin count problem
• Thinking about maximum coin value instead of ways
• Ignoring repeated use of coins

2. Which of the following TypeScript code snippets correctly initializes the DP array for the coin change ways problem for amount 5?

easy

A. const dp = new Array(5).fill(1);

B. const dp = new Array(6).fill(0); dp[0] = 1;

C. const dp = new Array(5).fill(0); dp[1] = 1;

D. const dp = new Array(6).fill(1); dp[0] = 0;

Solution

1. Step 1: Understand DP array size and initialization

   For amount 5, dp array size should be 6 (0 to 5). dp[0] = 1 means one way to make amount 0.

2. Step 2: Check each option

   const dp = new Array(6).fill(0); dp[0] = 1; correctly creates dp of size 6, fills 0, sets dp[0]=1. Others have wrong size or initialization.

3. Final Answer:

   const dp = new Array(6).fill(0); dp[0] = 1; -> Option B

4. Quick Check:

   dp size = amount+1, dp[0] = 1 [OK]

Hint: DP array size = amount + 1, dp[0] = 1 [OK]

Common Mistakes:

• Using dp array size equal to amount instead of amount+1
• Not setting dp[0] = 1
• Filling dp with 1 instead of 0 initially

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

const coins = [1, 2];
const amount = 3;
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
  for (let x = coin; x <= amount; x++) {
    dp[x] += dp[x - coin];
  }
}
console.log(dp[amount]);

medium

A. 3

B. 0

C. 1

D. 2

Solution

1. Step 1: Trace dp updates for coin 1

   dp after coin 1: dp[1]=1, dp[2]=1, dp[3]=1 (only using coin 1)

2. Step 2: Trace dp updates for coin 2

   dp[2]+=dp[0]=1+1=2, dp[3]+=dp[1]=1+1=2; final dp = [1,1,2,2]

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Ways to make 3 with [1,2] = 2 [OK]

Hint: Add ways from smaller amounts using each coin [OK]

Common Mistakes:

• Not updating dp correctly inside nested loops
• Confusing dp[x] with dp[x - coin]
• Missing dp[0] = 1 initialization

4. Find the error in this TypeScript code for coin change ways and select the fix:

const coins = [1, 2, 3];
const amount = 4;
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let i = 0; i <= coins.length; i++) {
  for (let x = coins[i]; x <= amount; x++) {
    dp[x] += dp[x - coins[i]];
  }
}
console.log(dp[amount]);

medium

A. Use for (const coin of coins) instead of index loop

B. Initialize dp array with 1 instead of 0

C. Change loop to for (let i = 0; i < coins.length; i++)

D. Set dp[amount] = 0 before loops

Solution

1. Step 1: Identify loop index error

   The loop runs i from 0 to coins.length inclusive, causing out-of-bounds access at coins[coins.length].

2. Step 2: Fix loop condition

   Change to i < coins.length to avoid accessing undefined coin.

3. Final Answer:

   Change loop to for (let i = 0; i < coins.length; i++) -> Option C

4. Quick Check:

   Loop index must be less than array length [OK]

Hint: Use < length, not <= length for array loops [OK]

Common Mistakes:

• Using <= in for loop causing out-of-bounds error
• Not initializing dp[0] = 1
• Confusing index and value in loops

5. Given coins = [1, 3, 5] and amount = 7, how many total ways are there to make amount 7 using any number of these coins?

hard

A. 4

B. 8

C. 7

D. 6

Solution

1. Step 1: Initialize dp array and process coin 1

   dp size 8, dp[0]=1. Using coin 1, dp[x]=1 for x=1 to 7.

2. Step 2: Update dp with coin 3

   For x=3 to 7, dp[x]+=dp[x-3]: dp[3]=2, dp[4]=1+dp[1]=2, dp[5]=1+dp[2]=2, dp[6]=1+dp[3]=3, dp[7]=1+dp[4]=3.

3. Step 3: Update dp with coin 5

   For x=5 to 7, dp[5]+=dp[0]=2+1=3, dp[6]+=dp[1]=3+1=4, dp[7]+=dp[2]=3+1=4.

4. Step 4: Final dp array and answer

   Final dp[7] = 4 ways. The combinations are: 7x1, 4x1+1x3, 1x1+2x3, 2x1+1x5.

5. Final Answer:

   4 -> Option A

6. Quick Check:

   Count all combinations with coins [1,3,5] for 7 = 4 [OK]

Hint: Build dp adding ways coin by coin [OK]

Common Mistakes:

• Missing some combinations with multiple coins
• Confusing permutations with combinations
• Incorrect dp updates order