901. Online Stock Span - Detailed Explanation

Problem statement

Implement the StockSpanner class that collects daily stock price quotes and returns the stock span for each new price. The span of the stock price today is the maximum number of consecutive days, counting back from today, on which the price was less than or equal to today's price.

You must support two operations:

• StockSpanner() Initializes the object.
• next(price): Given today's stock price, returns the span of today's price.

Examples

Input
["StockSpanner","next","next","next","next","next","next","next"]
[[],         [100],[80], [60], [70], [60], [75], [85]]
Output
[null,       1,     1,     1,     2,     1,     4,     6]

Explanation
Day 1: price = 100 → span = 1 (just today)
Day 2: price = 80  → span = 1 (80 ≤ 80 only today)
Day 3: price = 60  → span = 1
Day 4: price = 70  → span = 2 (70 ≥ 60, then stops at 80)
Day 5: price = 60  → span = 1
Day 6: price = 75  → span = 4 (75 ≥ 60,70,60; stops at 80)
Day 7: price = 85  → span = 6 (85 ≥ all previous up to 100; stops at 100)

Constraints

• Total calls to next ≤ 10⁵
• 1 ≤ price ≤ 10⁵

This question is the canonical example of the monotonic stack pattern. A monotonic stack is a stack whose stored values stay ordered in one direction, here strictly decreasing from bottom to top. Every push first pops the entries it dominates, which restores that order, so each entry is pushed once and popped once. The pattern answers any question of the shape "how many positions back, or forward, until a larger value appears," which is why it holds a place in the list of recurring interview patterns.

Naive approach

For each call to next(price), scan backwards through the list of previously seen prices until you find a price greater than today's. Count how many you visited, including today.

prices = []  # stored list of past prices
def next(price):
  count = 1
  i = len(prices) - 1
  while i >= 0 and prices[i] <= price:
    count += 1
    i -= 1
  prices.append(price)
  return count

• Time per call: O(n) in the worst case
• Space: O(n) to store all prices

Many increasing prices in a row make this approach too slow, and the judge rejects it with Time Limit Exceeded, or TLE. Every call then rescans the whole history, so the total work grows quadratically in the number of calls.

Optimized approach with a monotonic stack

Maintain a stack of pairs (price, span) such that prices in the stack strictly decrease from bottom to top.

1. When next(price) is called:
   • Start with current_span = 1.
   • While the stack is not empty and stack.top.price ≤ price:
     • Pop (p, s) off the stack.
     • Add its span to current_span += s.
   • Push (price, current_span) onto the stack.
   • Return current_span.

This works because each pop discards a day whose price was at or below today's. That day already carries the count of its own consecutive run, so adding its span absorbs a whole block of days in one step. No day ever has to be scanned twice.

Why it is correct

• Stack invariant: each element's price is greater than any price below it.
• Spans accumulate exactly the count of consecutive lower or equal prices.

Complexity analysis

• Time: Amortized O(1) per next call. Each price is pushed once and popped at most once, so n calls cost O(n) in total.
• Space: O(n) for the stack in the worst case, which is a strictly decreasing input.