< Back




901. Online Stock Span

Daily stock prices are streamed to us, and we need to calculate the span of the stock price for each
day. What's a span? It's the number of consecutive days before the current day that have a stock
price less than or equal to the current day's price.

This is a fun problem that requires us to stare at the numbers for a bit. What we realize is that we
need to maintain a monotonically decreasing stack. As we encounter a new price, we pop off all prices
that are less than or equal to the current price. We also maintain each day's span in the
monotonically decreasing stack, allowing us to calculate the span for the current day - by nature of
the monotonically decreasing stack.

If we don't pop anything off of the monotonically decreasing stack, we know that the current day's
span is 1. After processing the stack, we append the current day with its span.

Finally, we join both stack and return the result.

The solution is as follows:


  class StockSpanner:

      def __init__(self):
          self.stack = []

      def next(self, price: int) -> int:
          res = 1

          while self.stack and price >= self.stack[-1][0]:
              res += self.stack.pop()[1]

          self.stack.append([price, res])
          return self.stack[-1][1]


_ Time Complexity:

  O(1) - Analysis of the monotonically increasing stack is O(1) per call to next.

_ Space Complexity:

  O(n) - In the worst case scenario, we have to store all n prices in the stack.