The Stock Span Problem (also featured as LeetCode 901: Online Stock Span) is a classic quantitative time-series algorithm. Given an array of daily stock price quotes arr[] of length $n$, the span span[i] on day $i$ is defined as the maximum number of consecutive trading days immediately preceding and including day $i$ for which the stock price was less than or equal to arr[i].

1. Problem Specification & Trace Examples

For each index $i \in [0, n - 1]$, we want to find the distance to the nearest preceding day $j < i$ such that $\text{arr}[j] > \text{arr}[i]$ (known as the Previous Greater Element index). If no such day exists, the span covers all days from day $0$ through day $i$, yielding $i + 1$.

• Example 1: arr = [100, 80, 60, 70, 60, 75, 85] → Output: [1, 1, 1, 2, 1, 4, 6]. On day 5 (price 75), the preceding prices [60, 70, 60] are all $\le 75$, stopping only at day 1 (price 80), giving a span of $5 - 1 = 4$. On day 6 (price 85), all prices back to day 1 (80) are $\le 85$, giving a span of $6 - 0 = 6$.
• Example 2: arr = [10, 4, 5, 90, 120, 80] → Output: [1, 1, 2, 4, 5, 1].

2. Why Naive Backward Scanning Degrades to O(n²)

A brute-force nested loop starts at index $i$ and walks backward ($j = i - 1, i - 2, \dots$) while $\text{arr}[j] \le \text{arr}[i]$. For strictly increasing price series (e.g., a bull market rally where every day sets a new high), the inner loop scans all $i$ previous elements on every step, resulting in $\sum_{i=0}^{n-1} i = O(n^2)$ comparisons—which times out when $n = 10^5$.

3. Optimal O(n) Monotonic Decreasing Stack Architecture

Notice a key structural invariant: if today's price $\text{arr}[i]$ is greater than or equal to yesterday's price $\text{arr}[j]$, then day $j$ can never be the "Previous Greater Element" for any future day $k > i$, because $\text{arr}[i]$ is both more recent and at least as large as $\text{arr}[j]$. Therefore, we can permanently pop all indices $j$ with $\text{arr}[j] \le \text{arr}[i]$ from a monotonic decreasing stack:

4. Production C++20 Implementation (Offline Batch Array)

#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> calculateSpan(const std::vector<int>& arr) {
        const int n = static_cast<int>(arr.size());
        std::vector<int> span(n, 1);
        std::stack<int> st; // Stores indices in strictly decreasing order of price

        for (int i = 0; i < n; ++i) {
            // Pop all previous days whose price is <= current day's price
            while (!st.empty() && arr[st.top()] <= arr[i]) {
                st.pop();
            }

            // If stack is empty, arr[i] is the highest price seen since day 0
            span[i] = st.empty() ? (i + 1) : (i - st.top());

            // Push current day index onto the monotonic stack
            st.push(i);
        }

        return span;
    }
};

5. Online Streaming Implementation in TypeScript (LeetCode 901)

When quotes arrive as a real-time WebSocket stream rather than a fixed array, we store [price, accumulatedSpan] tuples on the stack so we never need to retain the full historical array in memory:

export class StockSpanner {
  private readonly stack: Array<[price: number, span: number]> = [];

  public next(price: number): number {
    let currentSpan = 1;

    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
      const [, poppedSpan] = this.stack.pop()!;
      currentSpan += poppedSpan;
    }

    this.stack.push([price, currentSpan]);
    return currentSpan;
  }
}

6. Amortized Complexity Analysis

• Time Complexity — $O(n)$ Total / $O(1)$ Amortized per Day: Every index $i \in [0, n-1]$ is pushed onto the stack exactly once and popped at most once. Across all $n$ days, the while loop executes at most $n$ pops total, yielding strict $O(n)$ linear runtime.
• Auxiliary Space Complexity — $O(n)$: In the worst case of a strictly decreasing price series (e.g., [100, 90, 80, 70]), no elements are popped and the stack holds at most $n$ indices.