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?"