L15. Stock Span Problem | Stack and Queue

The Online Stock Span Problem is a classic algorithmic challenge from the Stack and Queue Data Structures and Algorithms (DSA) playlist. It requires computing the consecutive number of days for which the stock price was less than or equal to the current day's price, given a continuous stream of daily stock prices.

1. Problem Statement & Operational Mechanics

When analyzing stock market data, investors often look for historical patterns. The Stock Spanner problem evaluates incoming stock prices one by one and returns the "span" of each price.

• Definition of Span: The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the stock price was less than or equal to today's price.
• Input / Output Model:
  • You initialize a StockSpanner object.
  • You make repeated next(val) function calls passing an integer representing today's stock price.
  • Each next(val) call must return an integer representing the calculated span.

Step-by-Step Example Walkthrough

Consider the following sequence of stock prices received via next() calls: [7, 2, 1, 3, 3, 1, 8].

2. Real-Life Analogy & Mental Hook

Real-Life Analogy: Imagine standing on a stepped pyramid of crates, looking backward to your left. Each crate has its height painted on it. When you stand on a crate of height 3, you want to know how many consecutive crates immediately to your left are shorter than or equal to your height before you hit a taller crate that blocks your view.

In the brute force approach, you physically walk backward crate by crate. In the optimized Stack approach, you instantly remember where the "taller walls" are located, letting you leap past all the intermediate shorter crates in $O(1)$ amortized time.

3. Naive Approach: The Brute Force Solution

The Idea

Maintain a dynamic list (array) of all prices seen so far. Every time next(val) is called:

1. Append the new value to the dynamic list.
2. Initialize count = 1 (accounting for the current day).
3. Loop backward from the second-to-last index down to 0.
4. If the historical price is less than or equal to val, increment count. Otherwise, break out of the loop.
5. Return count.

Java-Style Implementation Blueprint

class StockSpanner {
    private List<Integer> list;

    public StockSpanner() {
        list = new ArrayList<>();
    }
    
    public int next(int price) {
        list.add(price);
        int count = 1;
        int n = list.size();
        
        // Iterate backwards from the second-to-last element
        for (int i = n - 2; i >= 0; i--) {
            if (list.get(i) <= price) {
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}

Performance Bottlenecks of Brute Force

• Time Complexity: $\mathcal{O}(N)$ per next() call in the worst case (e.g., strictly increasing prices like 1, 2, 3, 4, 5), where $N$ is the total number of days. Overall time for $N$ calls can degrade to $\mathcal{O}(N^2)$.
• Space Complexity: $\mathcal{O}(N)$ to store all stock prices in the dynamic list.
• Interviewer's Verdict: Unacceptable for high-frequency trading or large data streams because checking through the entire historical dataset on every call is too slow.

4. The Optimization Insight: Previous Greater Element (PGE)

To optimize the algorithm, we must avoid traversing backward through every single past element.

Why did the Brute Force fail?

It repeatedly checked elements that were smaller than the current price and had already been determined to be useless for future comparisons.

The Core Breakthrough

Instead of storing all historical values in a flat list, we can frame this problem as finding the Previous Greater Element (PGE) index:

• If we know the index of the closest historical day whose stock price was strictly greater than the current price, we can calculate the span instantly.
• Span Formula: $\text{Span} = \text{Current Index} - \text{Index of Previous Greater Element}$
• If no previous greater element exists (meaning all past prices are smaller), the span equals $\text{Current Index} - (-1)$, which correctly evaluates to $\text{Current Index} + 1$.

5. Step-by-Step Stack Dry Run

We utilize a Monotonic Decreasing Stack storing pairs: (price, index).

Let's trace [7, 2, 1, 3, 3, 1, 8] with our stack:

1. next(7) (Index 0):

   • Stack is empty.
   • Span = $0 - (-1) = 1$.
   • Push (7, 0) to Stack. Stack: [(7,0)]. Return 1.

2. next(2) (Index 1):

   • Top of stack is (7, 0). Since $7 > 2$, we keep it.
   • Span = $1 - 0 = 1$.
   • Push (2, 1) to Stack. Stack: [(7,0), (2,1)]. Return 1.

3. next(1) (Index 2):

   • Top of stack is (2, 1). Since $2 > 1$, we keep it.
   • Span = $2 - 1 = 1$.
   • Push (1, 2) to Stack. Stack: [(7,0), (2,1), (1,2)]. Return 1.

4. next(3) (Index 3):

   • Top of stack is (1, 2). Since $1 \le 3$, pop it! (It can never be the PGE for anything ahead since 3 is larger).
   • Next top is (2, 1). Since $2 \le 3$, pop it!
   • Next top is (7, 0). Since $7 > 3$, stop popping.
   • Span = $3 - 0 = 3$.
   • Push (3, 3) to Stack. Stack: [(7,0), (3,3)]. Return 3.

5. next(3) (Index 4):

   • Top is (3, 3). Since $3 \le 3$, pop it!
   • Next top is (7, 0). $7 > 3$, stop.
   • Span = $4 - 0 = 4$.
   • Push (3, 4) to Stack. Stack: [(7,0), (3,4)]. Return 4.

6. next(1) (Index 5):

   • Top is (3, 4). $3 > 1$, stop.
   • Span = $5 - 4 = 1$.
   • Push (1, 5) to Stack. Stack: [(7,0), (3,4), (1,5)]. Return 1.

7. next(8) (Index 6):

   • Top (1, 5) $\le 8 \rightarrow$ pop.
   • Top (3, 4) $\le 8 \rightarrow$ pop.
   • Top (7, 0) $\le 8 \rightarrow$ pop.
   • Stack is now empty.
   • Span = $6 - (-1) = 7$.
   • Push (8, 6) to Stack. Stack: [(8,6)]. Return 7.

6. Optimal Stack-Based Code Implementation

Below is the production-grade implementation in Java utilizing a monotonic stack of pairs (or custom node structures/arrays).

import java.util.Stack;
import java.util.AbstractMap.SimpleEntry;

class StockSpanner {
    private Stack<int[]> stack; // Stores pairs of {price, index}
    private int currentIndex;

    public StockSpanner() {
        stack = new Stack<>();
        currentIndex = -1;
    }
    
    public int next(int price) {
        currentIndex++;
        
        // Pop elements from the stack that are less than or equal to the current price
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            stack.pop();
        }
        
        // Calculate span: if stack is empty, all previous elements were smaller (-1 index)
        int span = stack.isEmpty() ? (currentIndex - (-1)) : (currentIndex - stack.peek()[1]);
        
        // Push the current price and its index onto the stack
        stack.push(new int[] { price, currentIndex });
        
        return span;
    }
}

7. Complexity Analysis

• Why amortized $\mathcal{O}(1)$? Every element is pushed into the stack exactly once and popped from the stack at most once across all $N$ function calls. Thus, the total work done across $N$ calls is bounded by $2N$ operations, averaging $\mathcal{O}(1)$ per call.

8. Summary and Key Takeaways

• Problem Definition: The stock span problem asks for the count of consecutive days going backward where stock prices were less than or equal to the current price.
• Brute Force Limitation: Iterating backward on every call results in $\mathcal{O}(N^2)$ time complexity, which fails under heavy loads.
• Mental Model Shift: Transform the problem into finding the Previous Greater Element (PGE) using indices.
• Monotonic Decreasing Stack: Maintain a stack of {price, index} pairs, popping smaller or equal elements since they can never act as a previous greater element for future prices.
• Span Calculation: Subtract the index of the previous greater element from the current index (currentIndex - stack.peek()[1]).
• Edge Case Handling: If the stack becomes empty after popping, it signifies that all prior elements were smaller, meaning the span spans from index 0 up to currentIndex (currentIndex - (-1)).
• Optimal Efficiency: Achieves amortized $\mathcal{O}(1)$ time complexity per next() call and $\mathcal{O}(N)$ overall space complexity.