Stock Span Problem Using Stack in DSA Typescript - Time & Space Complexity

Time Complexity: Stock Span Problem Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the stock span problem changes as the number of stock prices grows.

Specifically, how fast can we find the span for each price using a stack?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function calculateSpan(prices: number[]): number[] {
  const stack: number[] = [];
  const span: number[] = new Array(prices.length);

  for (let i = 0; i < prices.length; i++) {
    while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
      stack.pop();
    }
    span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
    stack.push(i);
  }

  return span;
}
    

This code calculates the stock span for each day using a stack to track indices of previous higher prices.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs once for each price.
• How many times: The while-loop inside may pop elements, but each element is pushed and popped at most once.

How Execution Grows With Input

As the number of prices grows, each price is processed once, and stack operations happen at most once per price.

Input Size (n)	Approx. Operations
10	About 20 (each price pushed and popped once)
100	About 200
1000	About 2000

Pattern observation: The total operations grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly in proportion to the number of prices.

Common Mistake

[X] Wrong: "The while-loop inside the for-loop makes this an O(n²) algorithm because it can run many times per price."

[OK] Correct: Each price index is pushed and popped only once, so the total number of while-loop iterations across all prices is at most n, not n times n.

Interview Connect

Understanding this stack-based approach shows you how to use data structures smartly to reduce repeated work, a key skill in coding interviews.

Self-Check

"What if we used a simple nested loop without a stack? How would the time complexity change?"

Practice

1. What does the Stock Span Problem calculate for each day in a list of stock prices?

easy

A. The average stock price over all days

B. The maximum stock price in the entire list

C. The number of consecutive days before the current day with a price less than or equal to the current day's price

D. The difference between the highest and lowest stock price

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds how many days in a row before today had prices less than or equal to today's price.

2. Step 2: Identify what is calculated for each day

   For each day, it counts consecutive previous days with prices not higher than current day.

3. Final Answer:

   The number of consecutive days before the current day with a price less than or equal to the current day's price -> Option C

4. Quick Check:

   Stock span = consecutive days with price ≤ current day price [OK]

Hint: Span counts days with price ≤ today's price backward [OK]

Common Mistakes:

• Thinking it finds max price overall
• Confusing span with price difference
• Calculating average price instead

2. Which TypeScript data structure is best suited to efficiently solve the Stock Span Problem?

easy

A. Stack

B. Array

C. Queue

D. Set

Solution

1. Step 1: Recall the problem needs to track previous prices efficiently

   We need to quickly find previous days with prices less or equal to current day.

2. Step 2: Identify the data structure that supports last-in-first-out access

   A stack allows pushing and popping previous prices to compare efficiently.

3. Final Answer:

   Stack -> Option A

4. Quick Check:

   Stack is used for last-in-first-out access [OK]

Hint: Use stack to track previous prices for quick comparison [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable
• Using set which does not maintain order
• Using array without stack logic

3. What is the output of the stock span array for prices [100, 80, 60, 70, 60, 75, 85]?

medium

A. [1, 1, 1, 2, 1, 3, 4]

B. [1, 1, 1, 1, 1, 1, 1]

C. [1, 2, 3, 4, 5, 6, 7]

D. [1, 1, 1, 2, 1, 4, 6]

Solution

1. Step 1: Calculate span for each day

   Day 0: 100 -> span 1 (no previous)
   Day 1: 80 ≤ 100 -> span 1
   Day 2: 60 ≤ 80 -> span 1
   Day 3: 70 > 60 -> span 2 (days 2 and 3)
   Day 4: 60 ≤ 70 -> span 1
   Day 5: 75 > 60, 70 -> span 4 (days 2,3,4,5)
   Day 6: 85 > 75, 70, 80 -> span 6 (days 1 to 6)

2. Step 2: Confirm final span array

   The spans are [1, 1, 1, 2, 1, 4, 6].

3. Final Answer:

   [1, 1, 1, 2, 1, 4, 6] -> Option D

4. Quick Check:

   Span array matches calculated values [OK]

Hint: Count consecutive previous days with price ≤ current day [OK]

Common Mistakes:

• Counting all previous days regardless of price
• Confusing span with cumulative sum
• Miscounting days when price increases

4. Identify the error in this TypeScript snippet for Stock Span calculation:

function calculateSpan(prices: number[]): number[] {
  const stack: number[] = [];
  const span: number[] = [];
  for (let i = 0; i < prices.length; i++) {
    while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
      stack.pop();
    }
    span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
    stack.push(i);
  }
  return span;
}

medium

A. The stack should store prices, not indices

B. The comparison operator should be <= instead of < in while condition

C. The span array is not initialized with zeros

D. The loop should start from i = 1, not 0

Solution

1. Step 1: Analyze the while loop condition

   The condition uses < to pop smaller prices, but equal prices should also be popped to count span correctly.

2. Step 2: Correct the comparison operator

   Change < to <= so that prices equal to current price are popped, ensuring correct span calculation.

3. Final Answer:

   The comparison operator should be <= instead of < in while condition -> Option B

4. Quick Check:

   Use <= to include equal prices in span [OK]

Hint: Use <= in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using < misses equal prices in span
• Storing prices instead of indices in stack
• Starting loop from 1 misses first day

5. Given stock prices [10, 4, 5, 90, 120, 80], how would you modify the standard Stock Span algorithm to also return the day index of the last higher price before each day? What is the output for the last higher price indices array?

hard

A. [-1, 0, 0, -1, -1, 4]

B. [-1, 0, 1, -1, -1, 4]

C. [-1, 0, 0, 2, 3, 3]

D. [-1, -1, 1, 0, 1, 2]

Solution

1. Step 1: Modify algorithm to track last higher price index

   Along with span, store index from stack top before popping. If stack empty, store -1.

2. Step 2: Calculate last higher price indices for each day

   Day 0 (10): no previous higher -> -1
   Day 1 (4): previous higher 10 at index 0 -> 0
   Day 2 (5): previous higher 10 at index 0 -> 0
   Day 3 (90): no previous higher -> -1
   Day 4 (120): no previous higher -> -1
   Day 5 (80): previous higher 120 at index 4 -> 4

3. Final Answer:

   [-1, 0, 0, -1, -1, 4] -> Option A

4. Quick Check:

   Last higher price indices match calculated values [OK]

Hint: Store stack top index before popping for last higher price [OK]

Common Mistakes:

• Returning span instead of last higher price indices
• Using price values instead of indices
• Assigning wrong indices when stack is empty