We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Online Stock Span

Difficulty: Medium

Problem Description

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

Key Insights

  • The span calculation requires checking previous prices until a higher price is encountered.
  • A stack can be used to store prices and their spans efficiently.
  • Each time a new price is added, the stack can help determine how many consecutive days had prices less than or equal to the current price in constant time.

Space and Time Complexity

Time Complexity: O(1) for each next call on average, O(n) in the worst case for a single call when all prices are in increasing order. Space Complexity: O(n) for storing the stack of prices and spans.

Solution

To solve the problem, we can utilize a stack data structure to keep track of the prices and their corresponding spans. When a new price is received, we pop elements from the stack while the current price is greater than or equal to the price at the top of the stack. This allows us to count the number of consecutive days where the price was less than or equal to the current price. The span for the current price is then calculated as the difference between the current day's index and the index of the last higher price (or the start if none exists). This approach ensures that each price is processed in constant time on average.

Code Solutions

class StockSpanner:
    def __init__(self):
        self.stack = []  # to store pairs of (price, span)

    def next(self, price: int) -> int:
        span = 1  # the span starts with the current day
        # Pop stack while the stack is not empty and the top price is less than or equal to the current price
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]  # Add the span of the popped price
        self.stack.append((price, span))  # Push the current price and its calculated span
        return span
← Back to All Questions