LeetCode 901 - Online Stock Span

The problem asks us to design a class that processes stock prices one day at a time and, for every new price, returns the stock span for that day.

leetcodemediumstackdesignmonotonic-stackdata-stream

LeetCode Problem 901

Difficulty: 🟡 Medium
Topics: Stack, Design, Monotonic Stack, Data Stream

Solution

Problem Understanding

The problem asks us to design a class that processes stock prices one day at a time and, for every new price, returns the stock span for that day.

The stock span is defined as the number of consecutive days ending today where the stock price was less than or equal to today's price. We start from the current day and move backward through previous days until we encounter a price greater than today's price. The count of all valid consecutive days is the span.

For example, suppose the incoming prices are:

100, 80, 60, 70, 60, 75, 85

When the current price is 75, we look backward:

75 >= 60  -> valid
75 >= 70  -> valid
75 >= 60  -> valid
75 < 80   -> stop

So the span is 4.

The input is not provided all at once. Instead, prices arrive incrementally through repeated calls to the next(price) method. This means the solution must work in an online fashion, processing one value at a time without recomputing everything from scratch.

The constraints are relatively small, at most 10^4 calls, but the intended solution is still expected to be efficient. A naive approach that scans backward for every query can degrade to quadratic time in the worst case, especially when prices are strictly increasing.

An important observation is that once we know a previous price is smaller than or equal to the current price, that previous price can never block future spans again. This observation leads naturally to a monotonic stack solution.

Several edge cases are important:

  • Strictly decreasing prices, where every span is 1
  • Strictly increasing prices, where spans grow continuously
  • Repeated equal prices, because the condition is <=, not <
  • A single price input
  • Large consecutive increasing sequences that would make a naive approach slow

The problem guarantees that all prices are positive integers and that the number of operations is bounded.

Approaches

Brute Force Approach

The simplest approach is to store all previous prices in an array. For every new price, we scan backward from the most recent day until we find a price greater than the current price.

For example:

Prices: [100, 80, 60, 70]
Current price: 70

We scan backward:

70 >= 60 -> count
70 < 80  -> stop

The span is 2.

This approach is correct because it directly implements the definition of span. However, it can become inefficient. In the worst case, if prices are strictly increasing, every query scans all previous elements.

Example:

1, 2, 3, 4, 5, 6

The work becomes:

1 + 2 + 3 + 4 + 5 + 6

which is O(n^2) overall.

Optimal Approach, Monotonic Stack

The key insight is that many previous prices become irrelevant once a larger price appears.

Suppose we have:

100, 80, 60, 70

When processing 70, the price 60 is popped because 70 is greater than or equal to it. After this happens, 60 can never matter again for future span calculations because 70 already dominates it and is more recent.

This suggests maintaining a monotonic decreasing stack. Each stack entry stores:

  • The stock price
  • The span associated with that price

When a new price arrives:

  • Pop all stack elements with price <= current price
  • Accumulate their spans
  • Push the new price with the combined span

This allows us to skip large groups of days at once instead of scanning individually.

Each element is pushed once and popped once, giving amortized O(1) time per operation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per query, O(n²) total O(n) Scans backward through all previous prices
Optimal O(1) amortized per query, O(n) total O(n) Uses a monotonic decreasing stack

Algorithm Walkthrough

  1. Initialize an empty stack.

The stack will store pairs of:

(price, span)

The stack is maintained in decreasing order of prices from bottom to top. 2. When a new price arrives, initialize the span as 1.

Every price always counts itself, so the minimum span is always 1. 3. While the stack is not empty and the top price is less than or equal to the current price, pop the stack.

These popped prices are guaranteed to be included in today's span because they are less than or equal to today's price. 4. Add the popped element's span to the current span.

Instead of counting days one by one, we reuse previously computed spans. This is the optimization that makes the algorithm efficient. 5. Push the pair (current_price, current_span) onto the stack.

This preserves the decreasing stack property. 6. Return the computed span.

Why it works

The stack always maintains prices in strictly decreasing order. Any smaller or equal price behind a larger recent price becomes irrelevant because the larger price already covers all spans that the smaller price could contribute to. By merging spans during popping, we efficiently compress consecutive valid days into a single stack entry. Since each element is pushed and popped at most once, the algorithm is both correct and efficient.

Python Solution

class StockSpanner:

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

    def next(self, price: int) -> int:
        span = 1

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

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

        return span

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

The implementation uses a stack where each element is a tuple containing a price and its span.

Inside __init__, we initialize an empty stack that persists across method calls. This is necessary because the class processes prices incrementally over time.

Inside next, we begin with span = 1 because the current day always counts toward its own span.

The while loop removes all previous prices that are less than or equal to the current price. Since those prices belong in the current span, their stored spans are added directly to the current span. This avoids rescanning individual days.

After all smaller or equal prices are removed, we push the current (price, span) pair onto the stack. At this point, the stack remains monotonically decreasing.

Finally, we return the computed span.

Go Solution

type Pair struct {
	price int
	span  int
}

type StockSpanner struct {
	stack []Pair
}

func Constructor() StockSpanner {
	return StockSpanner{
		stack: []Pair{},
	}
}

func (this *StockSpanner) Next(price int) int {
	span := 1

	for len(this.stack) > 0 &&
		this.stack[len(this.stack)-1].price <= price {

		top := this.stack[len(this.stack)-1]
		this.stack = this.stack[:len(this.stack)-1]

		span += top.span
	}

	this.stack = append(this.stack, Pair{
		price: price,
		span:  span,
	})

	return span
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Next(price);
 */

The Go implementation follows the same logic as the Python version but uses a struct named Pair to store (price, span) values.

Go slices are used to simulate the stack. Popping is performed with slicing:

this.stack = this.stack[:len(this.stack)-1]

Unlike Python, Go does not have built-in tuple support, so a custom struct is cleaner and more readable.

Integer overflow is not a concern because the maximum number of calls is only 10^4.

Worked Examples

Example 1

Input prices:

100, 80, 60, 70, 60, 75, 85
Day Price Stack Before Operations Span Stack After
1 100 [] push (100,1) 1 [(100,1)]
2 80 [(100,1)] no pop 1 [(100,1),(80,1)]
3 60 [(100,1),(80,1)] no pop 1 [(100,1),(80,1),(60,1)]
4 70 [(100,1),(80,1),(60,1)] pop (60,1) 2 [(100,1),(80,1),(70,2)]
5 60 [(100,1),(80,1),(70,2)] no pop 1 [(100,1),(80,1),(70,2),(60,1)]
6 75 [(100,1),(80,1),(70,2),(60,1)] pop (60,1), pop (70,2) 4 [(100,1),(80,1),(75,4)]
7 85 [(100,1),(80,1),(75,4)] pop (75,4), pop (80,1) 6 [(100,1),(85,6)]

Final output:

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

Why the Span for 85 is 6

When processing 85:

  • 75 contributes span 4
  • 80 contributes span 1
  • Current day contributes 1

Total:

4 + 1 + 1 = 6

The algorithm reuses previously computed spans instead of recounting days individually.

Complexity Analysis

Measure Complexity Explanation
Time O(1) amortized per call Each element is pushed and popped at most once
Space O(n) The stack may store all prices in decreasing order

Although the while loop may appear expensive, each stock price can only be removed from the stack one time. Across all operations, the total number of pushes and pops is linear. Therefore, the total runtime across n calls is O(n), which means each operation costs O(1) amortized time.

Test Cases

# Example from problem statement
spanner = StockSpanner()
assert spanner.next(100) == 1  # first element
assert spanner.next(80) == 1   # smaller than previous
assert spanner.next(60) == 1   # decreasing sequence
assert spanner.next(70) == 2   # spans across 60
assert spanner.next(60) == 1   # reset because previous is larger
assert spanner.next(75) == 4   # spans across multiple elements
assert spanner.next(85) == 6   # spans across most previous days

# Strictly increasing prices
spanner = StockSpanner()
assert spanner.next(10) == 1
assert spanner.next(20) == 2
assert spanner.next(30) == 3
assert spanner.next(40) == 4

# Strictly decreasing prices
spanner = StockSpanner()
assert spanner.next(40) == 1
assert spanner.next(30) == 1
assert spanner.next(20) == 1
assert spanner.next(10) == 1

# Equal prices
spanner = StockSpanner()
assert spanner.next(50) == 1
assert spanner.next(50) == 2
assert spanner.next(50) == 3

# Single element
spanner = StockSpanner()
assert spanner.next(999) == 1

# Alternating highs and lows
spanner = StockSpanner()
assert spanner.next(30) == 1
assert spanner.next(10) == 1
assert spanner.next(20) == 2
assert spanner.next(15) == 1
assert spanner.next(25) == 4

# Large increasing sequence stress test
spanner = StockSpanner()
for i in range(1, 101):
    assert spanner.next(i) == i  # each span grows by 1
Test Why
Problem example Validates core functionality
Strictly increasing prices Tests maximum span growth
Strictly decreasing prices Tests repeated span of 1
Equal prices Verifies <= handling
Single element Tests minimum input size
Alternating highs and lows Tests mixed stack operations
Large increasing sequence Stress tests amortized efficiency

Edge Cases

Strictly Decreasing Prices

A decreasing sequence such as:

100, 90, 80, 70

is an important edge case because no previous price is less than or equal to the current one. Every span should therefore be exactly 1.

A buggy implementation might accidentally merge spans incorrectly or fail to stop at larger values. The monotonic decreasing stack handles this naturally because no popping occurs.

Repeated Equal Prices

The condition uses <=, not <.

For example:

50, 50, 50

The spans should be:

1, 2, 3

If the implementation uses a strict < comparison, equal prices would not merge correctly and the spans would all incorrectly become 1.

The solution correctly handles this with:

while stack_top_price <= current_price

Strictly Increasing Prices

An increasing sequence such as:

10, 20, 30, 40, 50

is the worst case for the brute-force approach because every query scans all previous elements.

However, the monotonic stack solution remains efficient because each element is popped only once over the entire execution. This guarantees amortized constant time per operation.

Single Price Input

When only one price is processed, the span must always be 1.

This case verifies that the implementation correctly initializes the span before entering the loop and does not rely on previous elements existing in the stack.