Online Stock Span Visualization & Animation
Computes how many consecutive prior days had a price ≤ today using a monotonic stack with accumulated spans; O(1) amortized.
## What is it?
Design a data structure that answers "stock span" queries online: for each day's price, return how many consecutive days (including today) the price has been ≤ today's price.
## How it works
- Maintain a stack of `(price, span)` pairs
- For each new price:
- Initialize `span = 1`
- While the stack top price ≤ current price → add the span of the top to current span, pop
- Push `(current price, current span)` onto the stack
- Return the current span
## When to use
- Online stock span queries arriving one price at a time
- Problems asking for the "range of dominance" or "how far back does the current value win"
## Key Points
- O(1) amortized per query — each element is pushed and popped at most once across all queries
- O(n) space overall
- Monotonic decreasing price stack
- Great example of aggregating information into the stack itself (storing span, not just index)
Category: algorithms
Difficulty: intermediate
Time Complexity: O(1) amortized
Space Complexity: O(n)
View Online Stock Span Visualization