Buy and Sell Stocks All Variants in DSA Typescript - Time & Space Complexity

Time Complexity: Buy and Sell Stocks All Variants

O(n)

Understanding Time Complexity

When solving buy and sell stock problems, we want to know how the time needed grows as the number of days increases.

We ask: How does the number of price checks and decisions change when we have more days?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let maxProfit = 0;
  for (const price of prices) {
    if (price < minPrice) minPrice = price;
    else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
  }
  return maxProfit;
}
    

This code finds the best profit from buying and selling once by checking each day's price.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop through the prices array.
• How many times: Exactly once for each day (n times).

How Execution Grows With Input

As the number of days increases, the code checks each price once.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of days.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the number of days.

Common Mistake

[X] Wrong: "Checking every pair of days is needed to find max profit."

[OK] Correct: The code smartly tracks the lowest price so far and only compares current price to it, avoiding extra checks.

Interview Connect

Understanding this time complexity shows you can write efficient code that scales well, a key skill interviewers look for.

Self-Check

"What if we allowed unlimited transactions instead of just one? How would the time complexity change?"