Online Stock Span

Problem Description

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day.

The span of the stock’s price in one day is the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to the price of today.

• For example, if the prices of the stock in the last four days is [60, 70, 60, 80] and the price of today is 80, then the span of today is 4 because the starting from today, the product of the last four days was less than or equal to 80.
• If the prices of the stock in the last four days is [60, 70, 80, 75] and the price of today is 75, then the span of today is 1.

Implement the StockSpanner class:

• StockSpanner() Initializes the object of the class.
• int next(int price) Returns the span of the stock’s price given that today’s price is price.

Examples

Constraints

• 1 <= price <= 10⁵
• At most 10⁴ calls will be made to next.

Monotonic Decreasing Stack with Accumulation

To calculate the span of prices in O(1) amortized time, we can use a monotonic decreasing stack. The stack stores pairs of (price, span). When a new price is processed:

1. Initialize the current day’s span as 1.
2. 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 and add its span to the current span. (Since the popped price is smaller, its span represents days that are also smaller than our current price).
3. Push the pair (price, current_span) onto the stack and return current_span.

Solution 1: Monotonic Accumulator Stack

Push price and accumulated span tuples onto a decreasing stack.

import java.util.Stack;

class StockSpanner {
    private static class Node {
        int price;
        int span;
        Node(int price, int span) {
            this.price = price;
            this.span = span;
        }
    }

    private Stack<Node> stack;

    public StockSpanner() {
        stack = new Stack<>();
    }

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek().price <= price) {
            span += stack.pop().span; // accumulate spans of smaller days
        }
        stack.push(new Node(price, span));
        return span;
    }
}

class StockSpanner:
    def __init__(self):
        self.stack = []  # stores pairs of (price, span)

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

#include <stack>
#include <utility>

class StockSpanner {
private:
    std::stack<std::pair<int, int>> stack; // stores {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;
    }
};

Complexity Analysis

• Time Complexity: O(1) amortized time per next call. Each price is pushed to and popped from the stack at most once.
• Space Complexity: O(n) auxiliary space to store elements in the stack in the worst case (e.g. strictly decreasing prices).

Where It Breaks

If we need to query random historical days rather than just returning the span of the current day, this stack-based compression is not sufficient, and a segment tree is required.

Common Mistakes

• Incorrect check conditions: Using < instead of <= when checking the top of the stack. The problem requires days where the price was less than or equal to the current day.
• Calculating spans by rescanning: Storing all prices in a list and iterating backward on every next call, which takes O(n) time per call and O(n²) total.

Frequently Asked Questions

Why does this count as O(1) amortized time? Each incoming day is pushed onto the stack exactly once. Although a single next call can trigger many pop operations, the total number of pops over the lifespan of the object cannot exceed the number of elements pushed, yielding O(1) average time.

What happens if the price is strictly decreasing? No elements are popped from the stack, and every call to next returns 1. The stack will grow to size n.

← All Problems