Coin Change Minimum Coins in DSA Typescript - Time & Space Complexity

Time Complexity: Coin Change Minimum Coins

O(amount x coins.length)

Understanding Time Complexity

We want to understand how the time needed to find the minimum coins changes as the amount grows.

How does the number of steps grow when we try to make bigger amounts with given coins?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function minCoins(coins: number[], amount: number): number {
  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];
}
    

This code finds the fewest coins needed to make a given amount using the coins available.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each amount from 1 to the target, we check all coins.
• How many times: Outer loop runs amount times; inner loop runs coins.length times for each outer iteration.

How Execution Grows With Input

As the amount grows, the steps grow by roughly the amount times the number of coins.

Input Size (amount)	Approx. Operations
10	10 x coins.length
100	100 x coins.length
1000	1000 x coins.length

Pattern observation: The work grows linearly with the amount and linearly with the number of coins.

Final Time Complexity

Time Complexity: O(amount x coins.length)

This means the time needed grows proportionally with the amount and the number of coin types.

Common Mistake

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

[OK] Correct: Each coin is checked for every amount, so more coins mean more checks and more time.

Interview Connect

Understanding this complexity helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we used recursion with memoization instead of loops? How would the time complexity change?"