Online Stock Span

Problem Description

Design an algorithm that collects daily price quotes for a stock and returns the span of that stock's price for the current day. The span is defined as the maximum number of consecutive days (including today and going backwards) over which the stock price was less than or equal to today's price.

Key Insights

• The problem can be solved efficiently using a monotonic stack.
• Store pairs of (price, span) in the stack, where span is the number of consecutive days whose prices are less than or equal to that price.
• For every new price, pop elements from the stack while they are less than or equal to the current price, and accumulate their spans.
• This approach ensures that each price is processed only once, leading to an amortized O(1) time per operation.

Space and Time Complexity

Time Complexity: Amortized O(1) per call to next Space Complexity: O(n) where n is the number of price quotes stored in the stack

Solution

We use a monotonic stack to keep track of prices and their associated spans. Each time the next price is introduced, we:

1. Initialize a span value of 1 for the current day.
2. While the stack is not empty and the price at the top of the stack is less than or equal to the current price, pop the pair and add its span to the current span.
3. Push the current price and its computed span onto the stack.
4. Return the span.

This works because the popped elements represent a sequence of consecutive days where the stock prices were less than or equal to the current price.

Code Solutions