Stock Span Problem Using Stack in DSA C - Execution Trace

Concept Flow - Stock Span Problem Using Stack

Start with empty stack

↓

For each day's price

↓

While stack not empty and top price <= current price

↓

Pop from stack

↓

If stack empty -> span = current day index + 1

↓

Else span = current day index - top index on stack

↓

Push current day index onto stack

↓

Move to next day

↓

Repeat until all days processed

↓

Return span array

The flow shows how for each day's price, we pop smaller or equal prices from stack to find the span, then push current day index.

Execution Sample

DSA C

prices = [100, 80, 60, 70, 60, 75, 85];
stack = empty;
for i in range(len(prices)) {
  while stack not empty and prices[stack.top] <= prices[i]:
    stack.pop();
  span[i] = stack empty ? i+1 : i - stack.top;
  stack.push(i);
}

Calculates stock span for each day using a stack to track indices of days with higher prices.

Execution Table

Step	Operation	Current Day (i)	Price	Stack (indices)	Span Array	Visual State
1	Start	-	-	[]	[]	Stack empty, no spans computed
2	Process day 0	0	100	[]	[1]	Stack empty, span = 0+1=1, push 0 -> stack=[0]
3	Process day 1	1	80	[0]	[1, ?]	Top price 100 > 80, span=1-0=1, push 1 -> stack=[0,1]
4	Process day 2	2	60	[0,1]	[1,1,?]	Top price 80 > 60, span=2-1=1, push 2 -> stack=[0,1,2]
5	Process day 3	3	70	[0,1,2]	[1,1,1,?]	Pop 2 (60 <=70), stack=[0,1]; top price 80 >70, span=3-1=2, push 3 -> stack=[0,1,3]
6	Process day 4	4	60	[0,1,3]	[1,1,1,2,?]	Top price 70 > 60, span=4-3=1, push 4 -> stack=[0,1,3,4]
7	Process day 5	5	75	[0,1,3,4]	[1,1,1,2,1,?]	Pop 4 (60 <=75), stack=[0,1,3]; pop 3 (70 <=75), stack=[0,1]; top price 80 >75, span=5-1=4, push 5 -> stack=[0,1,5]
8	Process day 6	6	85	[0,1,5]	[1,1,1,2,1,4,?]	Pop 5 (75 <=85), stack=[0,1]; pop 1 (80 <=85), stack=[0]; top price 100 >85, span=6-0=6, push 6 -> stack=[0,6]
9	End	-	-	[0,6]	[1,1,1,2,1,4,6]	All days processed, final span array computed

💡 All days processed, loop ends.

Variable Tracker

Variable	Start	After Day 0	After Day 1	After Day 2	After Day 3	After Day 4	After Day 5	After Day 6	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]

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 their span is included in current day's span. This is shown in steps 5, 7, and 8 where popping happens before calculating span.

Why is the span for day 0 equal to 1 even though the stack is empty?

When stack is empty, it means no previous higher price exists, so span is current day index + 1. Step 2 shows this with span=1 for day 0.

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

Indices help calculate span by subtracting positions. Also, prices can be accessed via indices. This is clear in the span calculation in steps 3-8.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What is the span calculated for day 3?

A 1

B 3

C 2

D 4

💡 Hint

Check the 'Span Array' column at step 5 in the execution table.

At which step does the stack first contain three indices?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Stack (indices)' column to see when it reaches length 3.

If the price on day 6 was 50 instead of 85, what would happen to the span at day 6?

A Span would be 1

B Span would be 7

C Span would be 2

D Span would be 6

💡 Hint

Consider that price 50 is less than previous prices, so no popping occurs, span = i - top index.

Concept Snapshot

Stock Span Problem Using Stack:
- Use a stack to store indices of days with higher prices.
- For each day, pop stack while top price <= current price.
- If stack empty, span = current day index + 1.
- Else span = current day index - top index on stack.
- Push current day index onto stack.
- Repeat for all days to get span array.

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had prices less than or equal to the current day's price. We use a stack to keep track of indices of days with higher prices. For each day, we pop from the stack all indices whose prices are less than or equal to the current price. If the stack becomes empty, the span is the current day index plus one, meaning all previous days had lower prices. Otherwise, the span is the difference between the current day index and the top index on the stack. We then push the current day index onto the stack and continue. This process efficiently computes the span for each day in one pass. The execution table shows step-by-step how the stack and span array change, and the variable tracker records the stack and span after each day. Key moments clarify why popping happens and why indices are stored. The visual quiz tests understanding of these steps.