Stock Span Problem Using Stack in DSA Typescript - Execution Trace

Concept Flow - Stock Span Problem Using Stack

Start with empty stack

↓

For each price in array

↓

While stack not empty and top price <= current price

↓

Pop from stack

↓

Calculate span: current index - top of stack index or current index + 1 if stack empty

↓

Push current index onto stack

↓

Move to next price

↓

Repeat until all prices processed

↓

Return span array

We use a stack to keep indexes of days with higher prices. For each day, pop smaller prices, then calculate span using stack top.

Execution Sample

DSA Typescript

function calculateSpan(prices: number[]): number[] {
  const stack: number[] = [];
  const span: number[] = [];
  for (let i = 0; i < prices.length; i++) {
    while (stack.length && 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;
}

Calculates stock span for each day using a stack to track previous higher prices.

Execution Table

Step	Operation	Current Index (i)	Stack (indexes)	Span Array	Visual State
1	Start	-	[]	[]	Stack empty, span empty
2	Process price 100	0	[]	[1]	Stack empty, span[0] = 0+1=1, push 0 -> stack=[0]
3	Process price 80	1	[0]	[1,1]	Top price 100 > 80, no pop, span[1] = 1-0=1, push 1 -> stack=[0,1]
4	Process price 60	2	[0,1]	[1,1,1]	Top price 80 > 60, no pop, span[2] = 2-1=1, push 2 -> stack=[0,1,2]
5	Process price 70	3	[0,1,2]	[1,1,1,2]	Pop 2 (60 <= 70), top now 1(80)>70 no pop, span[3]=3-1=2, push 3 -> stack=[0,1,3]
6	Process price 60	4	[0,1,3]	[1,1,1,2,1]	Top price 70 > 60 no pop, span[4]=4-3=1, push 4 -> stack=[0,1,3,4]
7	Process price 75	5	[0,1,3,4]	[1,1,1,2,1,4]	Pop 4(60<=75), pop 3(70<=75), top 1(80)>75 no pop, span[5]=5-1=4, push 5 -> stack=[0,1,5]
8	Process price 85	6	[0,1,5]	[1,1,1,2,1,4,6]	Pop 5(75<=85), pop 1(80<=85), top 0(100)>85 no pop, span[6]=6-0=6, push 6 -> stack=[0,6]
9	End	-	[0,6]	[1,1,1,2,1,4,6]	All prices processed, final span array returned

💡 All prices processed, loop ends

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
stack	[]	[0]	[0,1]	[0,1,2]	[0,1,3]	[0,1,3,4]	[0,1,5]	[0,6]	[0,6]
span	[]	[1]	[1,1]	[1,1,1]	[1,1,1,2]	[1,1,1,2,1]	[1,1,1,2,1,4]	[1,1,1,2,1,4,6]	[1,1,1,2,1,4,6]
i	-	0	1	2	3	4	5	6	-

Key Moments - 3 Insights

Why do we pop from the stack while the top price is less than or equal to the current price?

Because those days have prices not greater than current, so they don't limit the span. We remove them to find the last day with a higher price, as shown in steps 5, 7, and 8 in execution_table.

What does it mean when the stack is empty before calculating span?

It means no previous day has a higher price, so the span is the entire length from day 0 to current day (i+1). This happens at step 2 and is reflected in span calculation.

Why do we store indexes in the stack instead of prices?

Indexes help calculate the span by subtracting positions. Prices alone don't give position info. This is clear in the span calculation formula in the code and execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the stack content after processing price 70?

A [0,1,3]

B [0,1,2,3]

C [0,1]

D [0,1,2]

💡 Hint

Refer to execution_table row 5 under 'Stack (indexes)' column

At which step does the span for the current price become 4?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Check 'Span Array' column in execution_table for value 4

If the price at index 6 was 105 instead of 85, what would happen to the stack at step 8?

A Stack would contain [0,6]

B Stack would contain [6] only

C Stack would be empty before pushing index 6

D Stack would contain [0,1,5,6]

💡 Hint

Consider that 105 > all previous prices, so all get popped before pushing index 6

Concept Snapshot

Stock Span Problem Using Stack:
- Use a stack to store indexes of days with higher prices
- For each day, pop stack while top price <= current price
- Span = current index - top of stack index (or i+1 if stack empty)
- Push current index onto stack
- Result: span array showing consecutive days with price <= current day

Full Transcript

The Stock Span Problem calculates how many consecutive days before today had a price less than or equal to today's price. We use a stack to keep indexes of days with higher prices. For each price, we pop from the stack all indexes with prices less or equal to current price. If the stack is empty, the span is the entire length from day 0 to current day. Otherwise, span is difference between current index and top of stack index. We then push current index onto the stack. This process repeats for all prices. The execution table shows step-by-step stack changes and span array updates. Key moments clarify why we pop from stack, why stack emptiness matters, and why indexes are stored. The visual quiz tests understanding of stack state and span calculation at different steps. The snapshot summarizes the approach in simple steps.

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