Stock Span Problem Using Stack in DSA Python - 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 stack top

↓

Calculate span: current index - top of stack index

↓

Push current day index onto stack

↓

Repeat for all days

↓

Return spans array

We use a stack to keep track of indices of days with higher prices. For each day, we pop days with lower or equal prices, then calculate the span as the difference between current day and last higher price day.

Execution Sample

DSA Python

prices = [100, 80, 60, 70, 60, 75, 85]
stack = []
spans = []
for i, price in enumerate(prices):
    while stack and prices[stack[-1]] <= price:
        stack.pop()
    span = i + 1 if not stack else i - stack[-1]
    spans.append(span)
    stack.append(i)
print(spans)

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

Execution Table

Step	Operation	Current Day (i)	Current Price	Stack (Indices)	Span Calculated	Visual State (Prices with Spans)
1	Start	-	-	[]	-	[]
2	Process day 0	0	100	[] -> [0]	1	[100(1)]
3	Process day 1	1	80	[0]	1	[100(1), 80(1)]
4	Process day 2	2	60	[0,1]	1	[100(1), 80(1), 60(1)]
5	Process day 3	3	70	[0,1,2] -> pop 2	2	[100(1), 80(1), 60(1), 70(2)]
6	Process day 4	4	60	[0,1,3]	1	[100(1), 80(1), 60(1), 70(2), 60(1)]
7	Process day 5	5	75	[0,1,3,4] -> pop 4 -> pop 3	4	[100(1), 80(1), 60(1), 70(2), 60(1), 75(4)]
8	Process day 6	6	85	[0,1,5] -> pop 5 -> pop 1	6	[100(1), 80(1), 60(1), 70(2), 60(1), 75(4), 85(6)]
9	End	-	-	[0,6]	-	[100(1), 80(1), 60(1), 70(2), 60(1), 75(4), 85(6)]

💡 All days processed, spans calculated for each day.

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]
spans	[]	[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 elements from the stack when the current price is higher or equal?

Because those days have prices less or equal to current, so their span is included in current day's span. See execution_table rows 5, 7, and 8 where popping happens before calculating span.

Why do we use 'i + 1' as span when stack is empty?

If stack is empty, it means no previous day has higher price, so span is all days from day 0 to current day (i+1). Check execution_table row 2 for day 0.

What does the stack store and why indices instead of prices?

Stack stores indices to calculate span easily by subtracting indices. Prices alone don't give position info. This is shown in variable_tracker where stack holds indices.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the stack after popping?

A [0,3]

B [0,1,2]

C [0,1,3]

D [1,3]

💡 Hint

Check the 'Stack (Indices)' column at step 5 in execution_table.

At which step does the span for day 5 become 4?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at 'Span Calculated' column for day 5 in execution_table.

If the price on day 3 was 50 instead of 70, how would the span at step 5 change?

A Span would be 1

B Span would be 2

C Span would be 3

D Span would be 4

💡 Hint

Consider how popping depends on current price compared to stack top prices in execution_table.

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.
- Span = current index - top of stack index (or i+1 if stack empty).
- Push current day index onto stack.
- Result: spans array showing consecutive days with price <= current day.

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had stock prices less than or equal to today'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 days with prices less or equal to the current price. If the stack is empty, it means no previous higher price exists, so the span is the current day index plus one. Otherwise, the span is the difference between the current day index and the index on top of the stack. We then push the current day index onto the stack. This process continues for all days, resulting in an array of spans. The execution table shows each step, the stack state, and the spans calculated. Key moments clarify why popping happens, why we use indices, and how spans are computed. The visual quiz tests understanding of stack changes and span calculations.