📈 Design a StockSpanner

Ever wonder how financial apps calculate stock momentum in real-time? A common metric is the Stock Span. It measures how many consecutive days prior to today had a stock price less than or equal to today's price.

🏃‍♂️ The Problem at a Glance

We need to design a class StockSpanner that collects daily price quotes and returns the span for that day's price.

Example Walkthrough

Imagine a stream of stock prices arriving day by day: [100, 80, 60, 70, 60, 75, 85]

• Day 1: Price is 100. No previous days. Span = 1.
• Day 2: Price is 80. 80 < 100. Span = 1.
• Day 3: Price is 60. 60 < 80. Span = 1.
• Day 4: Price is 70. 70 > 60, but 70 < 80. It spans itself and the day with 60. Span = 2.
• Day 5: Price is 60. 60 < 70. Span = 1.
• Day 6: Price is 75. 75 is greater than 60, 70, and 60. Span = 4 (includes 75, 60, 70, 60).
• Day 7: Price is 85. 85 is greater than everything except 100. Span = 6.

❌ The Bruteforce Trap: $O(N)$ per call

The intuitive way to solve this is to store all prices in a list. Every time a new price comes in, you iterate backward to count how many elements are smaller or equal.

class StockSpannerNaive:
    def __init__(self):
        self.prices = []

    def next(self, price: int) -> int:
        span = 1
        # Look backward through history
        for i in range(len(self.prices) - 1, -1, -1):
            if self.prices[i] <= price:
                span += 1
            else:
                break
        self.prices.append(price)
        return span

Why this fails

If the stock prices are strictly increasing (e.g., [10, 20, 30, 40, 50]), every single call to next() scans the entire history. For $N$ days, the total time complexity skyrockets to $O(N^2)$.

---

💡 The Core Insight: We Only Care About Key Milestones

Look closely at Day 6 (75) and Day 7 (85) from our walkthrough:

• When 75 arrived, it completely swallowed up the history of 60, 70, and 60.
• Any future price larger than 75 will automatically be larger than those swallowed days.
• Any future price smaller than 75 will stop scanning at 75 anyway.

This means we don't need to store every single day individually. We can collapse past days into a single record: (price, accumulated_span).

By maintaining a monotonic decreasing stack (a stack where prices strictly decrease from bottom to top), we can pop smaller elements and accumulate their spans in $O(1)$ amortized time.

---

🛠️ Step-by-Step Execution Plan

• Initialize a stack: Each entry in the stack will be a pair: [price, span].
• Process new price: When next(price) is called, start with an initial span = 1.
• Pop smaller elements: While the stack is not empty and the top element's price is less than or equal to the current price:Pop the top element.
• Add its span to our current span.
• Push and Return: Push the current [price, span] pair back onto the stack and return the span.

---

</> Python Implementation

class StockSpanner:

    def __init__(self):
        # The stack will store pairs of [price, span]
        self.stack = []

    def next(self, price: int) -> int:
        # Every day spans at least itself
        current_span = 1
        
        # Collapse all previous days with equal or smaller prices
        while self.stack and self.stack[-1][0] <= price:
            prev_price, prev_span = self.stack.pop()
            current_span += prev_span
            
        # Push the collapsed data back to the stack
        self.stack.append([price, current_span])
        
        return current_span

---

📊 Complexity Analysis

• Time Complexity: $O(1)$ Amortized

Even though there is a while loop inside the next() function, each price element is pushed onto the stack exactly once and popped from the stack at most once. Across $N$ calls, the total number of operations is bounded by $2N$. Therefore, the average time complexity per stream input is a blazing fast $O(1)$.

• Space Complexity: $O(N)$ In the worst-case scenario (a strictly decreasing price sequence like [100, 90, 80, 70]), no elements will ever be popped. The stack will grow linearly with the number of inputs, resulting in a space complexity of $O(N)$.

🎯 Wrap Up

The Online Stock Span problem is a stellar example of how a monotonic stack shifts a problem from a sluggish $O(N^2)$ time layout to an ultra-efficient $O(N)$ system. By storing aggregate historical data directly in our stack elements, we avoid redundant backward lookups entirely.