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

↓

Calculate span: current index - top of stack index

↓

Push current day index onto stack

↓

Repeat for all days

↓

Return span array

We use a stack to keep indexes of days with higher prices. For each day, we pop days with lower or equal prices, then calculate span using the top of stack.

Execution Sample

DSA Rust

let prices = vec![100, 80, 60, 70, 60, 75, 85];
let mut stack = Vec::new();
let mut span = Vec::new();
for i in 0..prices.len() {
  while !stack.is_empty() && prices[*stack.last().unwrap()] <= prices[i] {
    stack.pop();
  }
  let s = if stack.is_empty() { i + 1 } else { i - *stack.last().unwrap() };
  span.push(s);
  stack.push(i);
}

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

Execution Table

Step	Operation	Current Day (i)	Price	Stack (indexes)	Span Calculated	Visual State (Stack top -> price)
1	Start	-	-	[]	-	Empty stack
2	Process day 0	0	100	[]	1	[0] -> 100
3	Process day 1	1	80	[0]	1	[0,1] -> 100,80
4	Process day 2	2	60	[0,1]	1	[0,1,2] -> 100,80,60
5	Process day 3	3	70	[0,1]	2	[0,1,3] -> 100,80,70
6	Process day 4	4	60	[0,1,3]	1	[0,1,3,4] -> 100,80,70,60
7	Process day 5	5	75	[0,1,3]	4	[0,1,3,5] -> 100,80,70,75
8	Process day 6	6	85	[0,1,5]	6	[0,1,5,6] -> 100,80,75,85
9	End	-	-	[0,6]	-	Final stack with indexes 0 and 6

💡 All days processed, stack contains indexes of days with prices higher than last processed 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,3,5]	[0,1,5,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 higher than current day, so they don't limit the span. See execution_table rows 5,7,8 where popping happens before calculating span.

What happens if the stack is empty when calculating span?

It means no previous day has a higher price, so span is current day index + 1. This is shown in execution_table rows 2 and 3.

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

Indexes help calculate the span by subtracting positions. Prices alone can't give span length. This is clear in variable_tracker where stack holds indexes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5. What is the stack content after processing day 3?

A [3]

B [0,1,3]

C [0,3]

D [0,1,2,3]

💡 Hint

Check the 'Visual State (Stack top -> price)' column at Step 5 in execution_table.

At which step does the span value become 4 for the first time?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look at the 'Span Calculated' column in execution_table rows.

If the price on day 4 was 90 instead of 60, how would the stack change at Step 6?

A Stack would pop more elements before pushing day 4

B Stack would remain the same as original

C Stack would be empty after processing day 4

D Stack would only contain day 4

💡 Hint

Consider the popping condition in the code and how higher prices affect the stack.

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

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had prices less than or equal to today's price. We use a stack to keep indexes 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 is empty, the span is the current day index plus one. Otherwise, span is the difference between current day index and the top index on the stack. We then 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 with stack changes and span calculation. Key moments clarify why popping happens, what empty stack means, and why indexes are stored. The visual quiz tests understanding of stack state and span values at specific steps.

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 ending with 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 minimum stock price in the entire list

D. The difference between the current day's price and the previous day's price

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds, for each day, the length of consecutive days ending on that day where prices are less than or equal to the current day's price.

2. Step 2: Clarify what is calculated per day

   It counts days backward until a higher price is found, including the current day.

3. Final Answer:

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

4. Quick Check:

   Span counts consecutive lower/equal prices [OK]

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

Common Mistakes:

• Confusing span with max or min price
• Counting all previous days instead of consecutive ones
• Calculating price differences instead of counts

2. Which Rust data structure is most suitable to efficiently solve the Stock Span Problem?

easy

A. LinkedList

B. Vector (Vec) used as a stack

C. HashMap

D. BinaryHeap

Solution

1. Step 1: Identify the need for last-in-first-out access

   The Stock Span Problem requires checking previous days' prices in reverse order, which fits stack behavior.

2. Step 2: Choose Rust's stack implementation

   Rust's Vec can be used as a stack with push and pop operations efficiently.

3. Final Answer:

   Vector (Vec) used as a stack -> Option B

4. Quick Check:

   Vec as stack fits LIFO for span calculation [OK]

Hint: Use Vec as stack for efficient push/pop [OK]

Common Mistakes:

• Using HashMap which is unordered
• Using LinkedList which is less efficient
• Using BinaryHeap which is for priority, not order

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, 1, 2, 1, 4, 6]

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

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

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

Solution

1. Step 1: Calculate span for each price

   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 A

4. Quick Check:

   Span array matches calculated values [OK]

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

Common Mistakes:

• Counting all previous days instead of consecutive
• Mixing up indices when calculating spans
• Assuming spans always increase

4. Given this Rust snippet for Stock Span, what is the bug?

let mut stack: Vec<usize> = Vec::new();
let mut span = vec![0; prices.len()];
for i in 0..prices.len() {
    while !stack.is_empty() && prices[*stack.last().unwrap()] < prices[i] {
        stack.pop();
    }
    span[i] = if stack.is_empty() { i + 1 } else { i - stack.last().unwrap() };
    stack.push(i);
}

medium

A. The comparison should be <= instead of < in the while condition

B. The stack should store prices, not indices

C. The span calculation subtracts without dereferencing the last stack element

D. The span vector is initialized with zeros instead of ones

Solution

1. Step 1: Analyze span calculation line

   span[i] = if stack.is_empty() { i + 1 } else { i - stack.last().unwrap() } uses stack.last().unwrap() without dereferencing, so it subtracts usize - &usize causing a type error or wrong calculation.

2. Step 2: Correct dereferencing needed

   It should be i - *stack.last().unwrap() to get the usize value from reference.

3. Final Answer:

   The span calculation subtracts without dereferencing the last stack element -> Option C

4. Quick Check:

   Dereference stack.last() for correct subtraction [OK]

Hint: Dereference stack.last() before subtraction [OK]

Common Mistakes:

• Using < instead of <= (not critical here)
• Not dereferencing stack.last() causing errors
• Initializing span with zeros is correct here
• Stack must store indices, not prices

5. How would you modify the Stock Span algorithm to handle a stream of stock prices arriving one by one, efficiently updating the span each time?

hard

A. Store all prices in a vector and recalculate spans from scratch each time

B. Use a hash map to store price frequencies and compute span from frequencies

C. Use a queue to store prices and calculate span by counting elements

D. Use a stack to store pairs of (price, span) and update span by accumulating popped spans

Solution

1. Step 1: Understand streaming requirement

   For streaming prices, we must update span without reprocessing all previous data.

2. Step 2: Use stack with (price, span) pairs

   Store each price with its span. When a new price arrives, pop all smaller prices and add their spans to current span, then push new pair.

3. Step 3: Efficient update

   This approach allows O(1) amortized time per new price, updating span incrementally.

4. Final Answer:

   Use a stack to store pairs of (price, span) and update span by accumulating popped spans -> Option D

5. Quick Check:

   Stack with (price, span) pairs for streaming [OK]

Hint: Accumulate spans while popping smaller prices in stack [OK]

Common Mistakes:

• Recalculating spans from scratch each time (inefficient)
• Using queue which doesn't support needed access pattern
• Using hash map which doesn't track order