Online Stock Span

How it works

The brute force approach repeatedly scans the same elements. We can avoid this by using a monotonic decreasing stack that stores pairs of (price, span).

When a new price arrives, we pop all entries from the stack that have prices less than or equal to the current price. The span of the current day is 1 (for today) plus the sum of spans of all popped entries. This works because those popped entries represent consecutive days that are now "covered" by the current higher price.

The stack remains in decreasing order of prices, so each element is pushed and popped at most once across all operations.

Steps

1. Initialize an empty stack that stores pairs of (price, span).
2. For each next(price) call:
   • Start with span = 1 (counting today).
   • While the stack is not empty and the top price is less than or equal to the current price:
     • Pop the top element and add its span to the current span.
   • Push (price, span) onto the stack.
   • Return span.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Where n is the number of function calls.

Things to watch for

Using Strictly Less Than Instead of Less Than or Equal

The span includes all consecutive days where prices are less than or equal to the current price, not strictly less than. Using < instead of <= will undercount the span when previous days have the same price as today.

Forgetting to Include the Current Day in the Span

The span always includes the current day itself. When initializing the span counter, start with 1 (for today) before adding spans from popped elements. Starting with 0 will result in spans that are off by one.

Storing Only Prices Without Spans

Storing just prices on the stack requires recounting spans on every query, leading to O(n) per operation. The stack should store pairs of (price, span) so that when an element is popped, its accumulated span can be added directly to the current span in O(1) time.

class StockSpanner:

    def __init__(self):
        self.stack = []  # pair: (price, span)

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack[-1][1]
            self.stack.pop()
        self.stack.append((price, span))
        return span

class StockSpanner {
    stack<pair<int, int>> stack; // pair: (price, span)

public:
    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!stack.empty() && stack.top().first <= price) {
            span += stack.top().second;
            stack.pop();
        }
        stack.push({price, span});
        return span;
    }
};