Stock Span Problem Using Stack in DSA Go - 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

↓

Calculate span: current index - top of stack index

↓

Push current day index onto stack

↓

Repeat for all days

↓

Return span array

We process each day's price, popping from stack all days with prices less or equal, then calculate span using stack top, and push current day.

Execution Sample

DSA Go

prices := []int{100, 80, 60, 70, 60, 75, 85}
stack := []int{}
spans := make([]int, len(prices))
for i, price := range prices {
  for len(stack) > 0 && prices[stack[len(stack)-1]] <= price {
    stack = stack[:len(stack)-1]
  }
  if len(stack) == 0 {
    spans[i] = i + 1
  } else {
    spans[i] = i - stack[len(stack)-1]
  }
  stack = append(stack, i)
}

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

Execution Table

Step	Operation	Current Day (Index, Price)	Stack Before	Stack After	Span Calculated	Visual State
1	Process day 0	(0, 100)	[]	[0]	1	Stack: [0(100)] Span: [1]
2	Process day 1	(1, 80)	[0]	[0,1]	1	Stack: [0(100),1(80)] Span: [1,1]
3	Process day 2	(2, 60)	[0,1]	[0,1,2]	1	Stack: [0(100),1(80),2(60)] Span: [1,1,1]
4	Process day 3	(3, 70)	[0,1,2]	[0,1,3]	3 - 1 = 2	Pop 2(60) Stack: [0(100),1(80)] Span: [1,1,1,2]
5	Process day 4	(4, 60)	[0,1,3]	[0,1,3,4]	1	Stack: [0(100),1(80),3(70),4(60)] Span: [1,1,1,2,1]
6	Process day 5	(5, 75)	[0,1,3,4]	[0,1,5]	5 - 1 = 4	Pop 4(60), Pop 3(70) Stack: [0,1] Span: [1,1,1,2,1,4]
7	Process day 6	(6, 85)	[0,1,5]	[0,6]	6 - 0 = 6	Pop 5(75), Pop 1(80) Stack: [0] Span: [1,1,1,2,1,4,6]

💡 All days processed, spans calculated for each day.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
stack (indices)	[]	[0]	[0,1]	[0,1,2]	[0,1,3]	[0,1,3,4]	[0,1,5]	[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]

Key Moments - 3 Insights

Why do we pop elements from the stack when the current price is higher?

Because those days have prices less or equal to current, so their span ends before current day. See steps 4, 6, and 7 in execution_table where popping happens before calculating span.

Why do we calculate span as current index minus top of stack index?

The top of stack holds the last day with higher price. The span is the number of days since then, so span = current index - top index. See steps 4, 6, and 7 for this calculation.

What if the stack is empty when calculating span?

It means no previous day has higher price, so span is current day index + 1 (all days so far). See step 1 where stack is empty and span is 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the stack after processing day 3?

A [0,1,3]

B [0,1]

C [0,1,2,3]

D [3]

💡 Hint

Check 'Stack After' column in row for step 4 in execution_table.

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

A Step 5

B Step 6

C Step 7

D Step 3

💡 Hint

Look at 'Span Calculated' column in execution_table rows.

If the price on day 2 was 90 instead of 60, how would the stack change at step 3?

A Stack would pop day 1 and day 0

B Stack would remain the same as [0,1,2]

C Stack would pop day 2 only

D Stack would pop day 1 only

💡 Hint

Compare prices and popping condition in execution_table step 3.

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 with days count for which price was less or equal.

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had a price less 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 current price. If the stack becomes empty, the span is the current day index plus one. Otherwise, the span is the difference between current day index and the index at the top of the stack. Then we push the current day index onto the stack. This process repeats for all days, resulting in the span array. The execution table shows each step's stack state and span calculation, helping visualize how the stack changes and how spans are computed.

Practice

1. What does the stock span problem calculate for each day in a list of stock prices?

easy

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

B. The maximum stock price in the entire list

C. The difference between the highest and lowest stock price

D. The total sum of stock prices up to the current day

Solution

1. Step 1: Understand the problem definition

   The stock span for a day is the count of consecutive previous days with prices less than or equal to that day's price.

2. Step 2: Clarify what is being calculated

   It is not about maximum price or sums, but about consecutive days with lower or equal prices.

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 A

4. Quick Check:

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

Hint: Span counts consecutive days with price ≤ current day price [OK]

Common Mistakes:

• Confusing span with maximum price
• Thinking span is total sum of prices
• Ignoring consecutive days condition

2. Which Go data structure is best suited to efficiently solve the stock span problem?

easy

A. Stack

B. Array

C. Queue

D. Map

Solution

1. Step 1: Identify the data structure for tracking previous prices

   The stack helps keep track of indices of days with prices to compare efficiently.

2. Step 2: Understand why stack is efficient

   Stack allows popping smaller prices and quickly finding the last higher price day, enabling O(n) time complexity.

3. Final Answer:

   Stack -> Option A

4. Quick Check:

   Stack is used for efficient previous price tracking [OK]

Hint: Use stack to track previous days' prices efficiently [OK]

Common Mistakes:

• Using array leads to O(n²) time
• Queue does not support backward checks
• Map is not suitable for order-based checks

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

medium

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

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

C. [1, 1, 1, 1, 1, 1, 1]

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 (includes day 2)
   Day 4: 60 ≤ 70 -> span=1
   Day 5: 75 > 60, 70 -> span=4 (includes days 4,3,2)
   Day 6: 85 > 75, 70, 60, 80 -> span=6 (includes days 5,4,3,2,1)

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: Pop smaller prices from stack to count span [OK]

Common Mistakes:

• Counting all previous days instead of consecutive
• Not popping smaller prices from stack
• Confusing span with price values

4. Identify the bug in this Go code snippet for stock span calculation:

func calculateSpan(prices []int) []int {
    n := len(prices)
    span := make([]int, n)
    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && prices[stack[len(stack)-1]] <= prices[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            span[i] = i + 1
        } else {
            span[i] = i - stack[len(stack)-1]
        }
        stack = append(stack, i)
    }
    return span
}

medium

A. The loop should start from i = 1 instead of 0

B. The comparison operator should be <= instead of < in the inner loop

C. Span array is not initialized with correct size

D. Stack should store prices, not indices

Solution

1. Step 1: Analyze the inner loop condition

   The inner loop pops indices while the price at stack top is less than current price. It should pop while less than or equal to handle equal prices correctly.

2. Step 2: Understand impact of using < instead of <=

   Using < misses popping equal prices, causing incorrect span counts for equal prices.

3. Final Answer:

   The comparison operator should be <= instead of < in the inner loop -> Option B

4. Quick Check:

   Use <= to correctly handle equal prices [OK]

Hint: Use <= in comparison to handle equal prices correctly [OK]

Common Mistakes:

• Stack storing prices instead of indices
• Incorrect span array size
• Starting loop from wrong index

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

hard

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

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

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

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

Solution

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

   Use stack to store indices; for each day, pop while current price ≥ price at stack top. If stack empty, last higher index is -1; else top of stack is last higher index.

2. Step 2: Calculate last higher price indices for given prices

   Prices: [10,4,5,90,120,80]
   Day 0: empty -> -1
   Day 1: 10 > 4, no pop -> 0
   Day 2: 4 <= 5 pop 1, 10 > 5 -> 0
   Day 3: 5 <= 90 pop 2, 10 <= 90 pop 0, empty -> -1
   Day 4: 90 <= 120 pop 3, empty -> -1
   Day 5: 120 > 80, no pop -> 4

3. Final Answer:

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

4. Quick Check:

   Last higher indices track previous greater price day [OK]

Hint: Track last higher price index using stack top or -1 if empty [OK]

Common Mistakes:

• Returning span instead of last higher index
• Not handling empty stack case (-1)
• Confusing last higher index with span count