Stock Span Problem Using Stack in DSA Rust

Mental Model

We find how many consecutive days before today had stock prices less or equal to today's price using a stack to remember previous days.

Analogy: Imagine a line of people showing their heights. For each person, we count how many people before them are shorter or equal in height until we find a taller person.

Prices: [100, 80, 60, 70, 60, 75, 85]
Stack stores indices of days with prices in decreasing order
Stack top -> index of last higher price day

Initial:
Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: []
Span: []

Dry Run Walkthrough

Input: prices: [100, 80, 60, 70, 60, 75, 85]

Goal: Calculate span for each day showing how many consecutive previous days had price less or equal to current day

Step 1: Process day 0 (price 100): stack empty, push index 0

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0]
Span: [1]

Why: No previous days, span is 1

Step 2: Process day 1 (price 80): price 80 < price at stack top (100), push index 1

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0, 1]
Span: [1, 1]

Why: Previous price higher, span is 1

Step 3: Process day 2 (price 60): price 60 < price at stack top (80), push index 2

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0, 1, 2]
Span: [1, 1, 1]

Why: Previous price higher, span is 1

Step 4: Process day 3 (price 70): pop indices while price at top ≤ 70; pop index 2 (60), stop at index 1 (80), push index 3

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0, 1, 3]
Span: [1, 1, 1, 2]

Why: Count days with price ≤ 70 before day 3

Step 5: Process day 4 (price 60): price 60 < price at stack top (70), push index 4

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0, 1, 3, 4]
Span: [1, 1, 1, 2, 1]

Why: Previous price higher, span is 1

Step 6: Process day 5 (price 75): pop indices while price at top ≤ 75; pop index 4 (60), pop index 3 (70), stop at index 1 (80), push index 5

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0, 1, 5]
Span: [1, 1, 1, 2, 1, 4]

Why: Count days with price ≤ 75 before day 5

Step 7: Process day 6 (price 85): pop indices while price at top ≤ 85; pop index 5 (75), pop index 1 (80), stop at index 0 (100), push index 6

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Stack: [0, 6]
Span: [1, 1, 1, 2, 1, 4, 6]

Why: Count days with price ≤ 85 before day 6

Result:

Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85
Span: 1 -> 1 -> 1 -> 2 -> 1 -> 4 -> 6

Annotated Code

DSA Rust

use std::vec::Vec;

fn calculate_span(prices: &[i32]) -> Vec<usize> {
    let n = prices.len();
    let mut span = vec![0; n];
    let mut stack: Vec<usize> = Vec::new(); // stack stores indices

    for i in 0..n {
        // pop indices while current price >= price at stack top
        while let Some(&top) = stack.last() {
            if prices[top] <= prices[i] {
                stack.pop();
            } else {
                break;
            }
        }

        // if stack empty, span is i+1 else difference
        span[i] = if stack.is_empty() { i + 1 } else { i - stack.last().unwrap() };

        stack.push(i);
    }

    span
}

fn main() {
    let prices = vec![100, 80, 60, 70, 60, 75, 85];
    let span = calculate_span(&prices);
    for s in span {
        print!("{} ", s);
    }
    println!();
}

while let Some(&top) = stack.last() { if prices[top] <= prices[i] { stack.pop(); } else { break; } }

pop indices of days with prices less or equal to current day to find last higher price day

span[i] = if stack.is_empty() { i + 1 } else { i - stack.last().unwrap() };

calculate span as distance from last higher price day or full length if none

stack.push(i);

push current day index to stack for future comparisons

Output

1 1 1 2 1 4 6 

Complexity Analysis

Time: O(n) because each price index is pushed and popped at most once from the stack

Space: O(n) for the stack and span array to store indices and results

vs Alternative: Naive approach is O(n^2) by checking all previous days for each day, stack reduces it to O(n)

Edge Cases

empty prices array

returns empty span array without error

DSA Rust

let n = prices.len();

all prices equal

span increases by 1 each day because all previous prices are less or equal

DSA Rust

while let Some(&top) = stack.last() { if prices[top] <= prices[i] { stack.pop(); } else { break; } }

strictly decreasing prices

span is always 1 because no previous price is less or equal

DSA Rust

span[i] = if stack.is_empty() { i + 1 } else { i - stack.last().unwrap() };

When to Use This Pattern

When you need to find how many previous consecutive elements satisfy a condition relative to current, use a stack to track indices for efficient look-back.

Common Mistakes

Mistake: Not popping all smaller or equal prices from the stack, leading to incorrect span calculation
Fix: Use a loop to pop from stack while top price is less or equal to current price

Mistake: Calculating span as i - top instead of i - top or i + 1 when stack empty
Fix: Check if stack is empty to assign span as i+1, else difference from last higher price index

Summary

Calculates how many consecutive previous days had stock prices less or equal to current day using a stack.

Use when you want to efficiently find spans or counts of consecutive elements meeting a condition before current position.

The key insight is using a stack to remember indices of days with strictly higher prices to quickly find span boundaries.

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