Online Stock Span

Problem

Design a StockSpanner. next(price) returns the span — the number of consecutive prices today and back that are ≤ price.

Constraints

• 0 ≤ price ≤ 10⁵
• at most 10⁴ calls

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

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

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

Java

import java.util.*;

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

class Solution {}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.