Online Stock Span

Problem

Design a class StockSpanner that receives a stream of daily stock prices, one per call. Each time a new price arrives via next(price), return that day’s span: the number of consecutive days ending today (today included) on which the price was less than or equal to today’s price.

In other words, starting from today and walking backward, count how many days in a row have price <= today's price, stopping at the first strictly greater price.

Implement:

• StockSpanner() — initializes the object.
• next(price: int) -> int — records today’s price and returns today’s span.

Examples

Example 1

Calls: next(100), next(80), next(60), next(70), next(60), next(75), next(85) Output: 1, 1, 1, 2, 1, 4, 6 Explanation: for 75, the run of days with price ≤ 75 is [60, 70, 60, 75], so the span is 4; 80 stops it.

Example 2

Calls: next(10), next(20), next(30) Output: 1, 2, 3 Explanation: each new price beats everything before it, so the span keeps growing.

Example 3

Calls: next(50), next(50) Output: 1, 2 Explanation: “less than or equal” means an equal price extends the span.

Constraints

• 1 <= price <= 10^5
• At most 10^4 calls to next — so an O(n) per call rescan is borderline O(n²) overall and the intended solution is amortized O(1) per call.

Think about it first

TL;DR

Monotonic decreasing stack of (price, span) pairs — amortized O(1) time per next call, O(n) space.

Approach 1 — Brute force

Store every price in a list. On each next, walk backward from the end counting days while price <= today.

class StockSpanner:
    def __init__(self) -> None:
        self.prices: list[int] = []

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

Complexity: O(n) per call, O(n²) over n calls; O(n) space. A monotonically increasing price stream makes every call rescan the whole history, so 10^4 calls costs ~10^8 comparisons in the worst case — too slow by design.

Approach 2 — Monotonic decreasing stack

The insight: if today’s price beats an earlier day’s price, that earlier day is permanently “shadowed” — no future day will ever stop its backward walk there, because today stops it first. So dominated days can be merged into the day that dominates them. Keep a stack of (price, span) pairs whose prices are strictly decreasing from bottom to top; each pair represents one visible day plus all the shadowed days it absorbed. This is the classic monotonic stack technique: a stack that maintains sorted order by popping violating elements, giving each element one push and one pop total.

class StockSpanner:
    def __init__(self) -> None:
        self.stack: list[tuple[int, int]] = []  # (price, span)

    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

Walkthrough of Example 1 — 100, 80, 60, 70, 60, 75, 85:

Output 1, 1, 1, 2, 1, 4, 6 matches.

Complexity: amortized O(1) per call (each price is pushed once and popped at most once, so n calls do at most 2n stack operations); O(n) space in the worst case (strictly decreasing prices never pop).

Common pitfalls

• Popping on < instead of <= — equal prices must extend the span (50, 50 → spans 1, 2).
• Forgetting to start span = 1 (today always counts) before absorbing popped spans.
• Storing bare prices instead of (price, span) pairs — after popping you lose the count of shadowed days and the answer undercounts.
• Assuming per-call worst case is O(1): a single call can pop the entire stack; the O(1) bound is amortized.

Pattern takeaway

When each new element only cares about the nearest previous element that is strictly greater (or smaller), elements in between are permanently irrelevant — pop them into an aggregate and keep the stack monotonic. Storing a compressed (value, count) pair on the stack turns “count everything back to the previous greater element” queries into amortized O(1) stream processing.