LeetCode 901: Online Stock Span

Problem Restatement

We need to design a class called StockSpanner.

The class receives stock prices one day at a time through the method next(price).

For each new price, we return its stock span.

The span is the number of consecutive days ending today where each price was less than or equal to today’s price.

For example:

prices = [100, 80, 60, 70, 60, 75, 85]

The spans are:

[1, 1, 1, 2, 1, 4, 6]

For price 75, the span is 4 because the last four prices are:

[60, 70, 60, 75]

All of them are less than or equal to 75.

Input and Output

The class shape is:

class StockSpanner:

    def __init__(self):
        ...

    def next(self, price: int) -> int:
        ...

Examples

Input:

stockSpanner = StockSpanner()
stockSpanner.next(100)
stockSpanner.next(80)
stockSpanner.next(60)
stockSpanner.next(70)
stockSpanner.next(60)
stockSpanner.next(75)
stockSpanner.next(85)

Output:

1
1
1
2
1
4
6

Step by step:

First Thought: Brute Force

A direct method is to store every price seen so far.

For each new price, walk backward through the list and count how many consecutive prices are less than or equal to the current price.

class StockSpanner:

    def __init__(self):
        self.prices = []

    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

This is correct, but it can be slow.

Problem With Brute Force

If prices keep increasing, each new call may scan all previous prices.

Example:

[10, 20, 30, 40, 50]

For 50, the method scans all five prices.

For many calls, the total cost can become quadratic.

We need to avoid rechecking prices that have already been absorbed into earlier spans.

Key Insight

When a previous price is less than or equal to today’s price, it belongs to today’s span.

If that previous price already had a span, then all prices inside that previous span also belong to today’s span.

So instead of storing only prices, store pairs:

(price, span)

The stack keeps prices in strictly decreasing order from bottom to top.

When a new price arrives, we pop every previous price that is less than or equal to it. Each popped item contributes its whole span.

This is the main compression.

For example, after processing:

[100, 80, 60, 70]

The stack is:

[(100, 1), (80, 1), (70, 2)]

The price 60 before 70 no longer needs its own stack entry because it has been included in the span of 70.

Algorithm

Maintain a stack of pairs:

(price, span)

For each next(price) call:

1. Start with span = 1 for today.
2. While the stack is not empty and the top price is less than or equal to price, pop it.
3. Add the popped span to the current span.
4. Push (price, span) onto the stack.
5. Return span.

The stack only keeps prices that can stop a future span.

A smaller or equal price below today’s price cannot stop any future span because today’s price is newer and at least as large.

Correctness

The stack stores groups of consecutive days.

Each pair (p, s) means there is a block of s consecutive days ending at price p, and every price in that block is less than or equal to p.

The stack is kept in decreasing price order.

When next(price) is called, every stack item with p <= price belongs to today’s span. Since its whole block also has prices less than or equal to p, every price in that block is also less than or equal to today’s price.

So we can safely add the whole stored span at once.

The popping stops when the stack is empty or the top price is greater than today’s price.

If the stack is empty, all previous grouped prices are less than or equal to today’s price, so the span includes all previous days plus today.

If the top price is greater, it is the nearest previous price that blocks the span. Any price before it cannot be included because the span must be consecutive.

Therefore, the algorithm returns exactly the number of consecutive days ending today whose prices are less than or equal to today’s price.

Complexity

A single call can pop many elements, but across all calls, each element can be removed only once.

Implementation

class StockSpanner:

    def __init__(self):
        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

Code Explanation

The stack stores compressed history:

self.stack = []

Each entry is:

(price, span)

For every new price, we count today first:

span = 1

Then we remove all previous prices that today’s price dominates:

while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]

The important part is adding the popped span, not just 1.

A popped entry may represent many previous days.

After all smaller or equal prices are absorbed, we store today’s compressed result:

self.stack.append((price, span))

Then we return the answer:

return span

Testing

def run_tests():
    s = StockSpanner()

    assert s.next(100) == 1
    assert s.next(80) == 1
    assert s.next(60) == 1
    assert s.next(70) == 2
    assert s.next(60) == 1
    assert s.next(75) == 4
    assert s.next(85) == 6

    s = StockSpanner()
    assert [s.next(x) for x in [10, 20, 30, 40]] == [1, 2, 3, 4]

    s = StockSpanner()
    assert [s.next(x) for x in [40, 30, 20, 10]] == [1, 1, 1, 1]

    s = StockSpanner()
    assert [s.next(x) for x in [50, 50, 50]] == [1, 2, 3]

    s = StockSpanner()
    assert [s.next(x) for x in [31, 41, 48, 59, 79]] == [1, 2, 3, 4, 5]

    print("all tests passed")

run_tests()

Test meaning: