074. Online Stock Span

Why this mechanism works

A smaller or equal previous price no longer blocks today's span. Store compressed blocks as (price,span). When a block's price is <= the new price, all days represented by that block can be absorbed at once. Strictly larger prices remain as barriers.

State and boundaries

stack has strictly decreasing block prices. Each block span counts consecutive days it summarizes.

Protocol

1. Start the incoming span at one.
2. Pop and add every block with price<=current.
3. Push the combined block.
4. Emit its span.

Visualization

prices: 100 80 60 70 60 75 85
spans:    1  1  1  2  1  4  6
75 absorbs blocks (60,1) and (70,2)

Python implementation

def stock_spans(prices):
    stack = []
    output = []
    for price in prices:
        span = 1
        while stack and stack[-1][0] <= price:
            span += stack.pop()[1]
        stack.append((price, span))
        output.append(span)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 stock_spans: stack = []
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[]

L3 stock_spans: output = []
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[]; output=[]

L4 stock_spans: for price in prices:
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[]; output=[]; price=100

L5 stock_spans: span = 1
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[]; output=[]; price=100; span=1

L8 stock_spans: stack.append((price, span))
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1)]; output=[]; price=100; span=1

L9 stock_spans: output.append(span)
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1)]; output=[1]; price=100; span=1

L4 stock_spans: for price in prices:
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1)]; output=[1]; price=80; span=1

L8 stock_spans: stack.append((price, span))
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1), (80, 1)]; output=[1]; price=80; span=1

... 19 intermediate state changes omitted ...

L7 stock_spans: span += stack.pop()[1]
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1), (80, 1)]; output=[1, 1, 1, 2, 1, 4]; price=85; span=5

L7 stock_spans: span += stack.pop()[1]
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1)]; output=[1, 1, 1, 2, 1, 4]; price=85; span=6

L8 stock_spans: stack.append((price, span))
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1), (85, 6)]; output=[1, 1, 1, 2, 1, 4]; price=85; span=6

L9 stock_spans: output.append(span)
prices=[100, 80, 60, 70, 60, 75, 85]; stack=[(100, 1), (85, 6)]; output=[1, 1, 1, 2, 1, 4, 6]; price=85; span=6

L2 stock_spans: stack = []
prices=[5, 5, 5]; stack=[]

L3 stock_spans: output = []
prices=[5, 5, 5]; stack=[]; output=[]

L4 stock_spans: for price in prices:
prices=[5, 5, 5]; stack=[]; output=[]; price=5

L5 stock_spans: span = 1
prices=[5, 5, 5]; stack=[]; output=[]; price=5; span=1

L8 stock_spans: stack.append((price, span))
prices=[5, 5, 5]; stack=[(5, 1)]; output=[]; price=5; span=1

L9 stock_spans: output.append(span)
prices=[5, 5, 5]; stack=[(5, 1)]; output=[1]; price=5; span=1

L7 stock_spans: span += stack.pop()[1]
prices=[5, 5, 5]; stack=[]; output=[1]; price=5; span=2

L8 stock_spans: stack.append((price, span))
prices=[5, 5, 5]; stack=[(5, 2)]; output=[1]; price=5; span=2

... 1 intermediate state changes omitted ...

L5 stock_spans: span = 1
prices=[5, 5, 5]; stack=[(5, 2)]; output=[1, 2]; price=5; span=1

L7 stock_spans: span += stack.pop()[1]
prices=[5, 5, 5]; stack=[]; output=[1, 2]; price=5; span=3

L8 stock_spans: stack.append((price, span))
prices=[5, 5, 5]; stack=[(5, 3)]; output=[1, 2]; price=5; span=3

L9 stock_spans: output.append(span)
prices=[5, 5, 5]; stack=[(5, 3)]; output=[1, 2, 3]; price=5; span=3

Why the solution is correct

Every absorbed block contains only prices no greater than its representative price, which is no greater than today. These adjacent blocks therefore all belong to today's span. The first remaining greater price is the exact stopping barrier.

Time and space

O(n) total time and O(n) worst-case space; a single insertion may pop many blocks but each block is removed once.

Common mistakes

Using < instead of <= incorrectly treats equal prices as barriers. Counting popped blocks rather than their stored spans undercounts compressed history.

Reasoning card

Transfer exercise

Turn this into an online next(price) class and explain the difference between worst-case and amortized update time.