Online Stock Span

Problem in plain words

Design a StockSpanner that receives one daily price at a time through next(price). Each call must return today's span: the number of consecutive days, ending today and counting backwards, on which the price was less than or equal to today's price. Today always counts, so the span is at least 1.

For example, after prices 10, 20, 15, a new price 18 has span 2 (15 and 18), because 20 breaks the streak.

Intuition

If yesterday's price is not higher than today's, then today's span swallows yesterday's entire span too, since every day inside it was also not higher. So we never need those swallowed days again; one entry holding the combined span replaces them. Keep a stack of (price, span) pairs with strictly decreasing prices. A new price pops every pair with a price less than or equal to it, adds their spans to its own, and pushes the merged result.

Approach

1. The constructor creates an empty stack of pairs.
2. In next(price), start with span = 1 for today.
3. While the stack is not empty and the top price is <= price, pop it and add its span to span.
4. Push (price, span) and return span.

Dry run

Calls: next(30), next(25), next(28), next(40), next(35), next(35).

Java solution

class StockSpanner {
    // Each entry is {price, span}; prices strictly decrease from bottom to top.
    private final Deque<int[]> stack;

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

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[] {price, span});
        return span;
    }
}

Python solution

class StockSpanner:
    def __init__(self):
        # Each entry is (price, span); prices strictly decrease bottom to top.
        self.stack = []

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

Complexity

Edge cases and common mistakes

• Equal prices: the span counts days with price less than or equal, so pop on <=. Using < breaks the streak at a repeated price.
• Forgetting today: the span starts at 1, not 0.
• Storing every price and scanning back: that is O(n) per call and O(n^2) overall on a long rising series, while the stack keeps the total linear.
• Storing only prices: without the merged span you cannot know how many days a popped entry represented. Store (price, span) or store indices instead.