Problem

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 today is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today’s price.

  • For example, if the price of a stock over the next 7 days were [100,80,60,70,60,75,85], then the stock spans would be [1,1,1,2,1,4,6].

Implement the StockSpanner class:

  • StockSpanner() Initializes the object of the class.
  • int next(int price) Returns the span of the stock’s price given that today’s price is price.

Examples

Example 1:

Input:
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output:
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

Solution

Method 1 - Using Monotonic Decreasing Stack

We should maintain a stack containing pairs of (current price, span of consecutive days) since we do not have direct access to indices.

For each new price, pop all elements from the stack with lower or equal prices, accumulating their spans.

Here is the approach:

The StockSpanner class needs to efficiently compute the span of the stock price for the current day based on historical prices. This can be achieved using a monotonic stack that tracks prices and their respective spans. The algorithm works as follows:

  1. Initialization: A stack is used to store pairs of (price, span).
  2. Processing:
    • For each new price, initialize the span as 1.
    • While there are prices on the stack that are less than or equal to the current price, pop them and add their spans to the current span.
    • Push the current price and its span onto the stack.
  3. Result: Return the computed span.

Code

Java
class StockSpanner {

    Stack<int[]> stack;

    public StockSpanner() {
        stack = new Stack<>();
    }

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && price >= stack.peek()[0]) {
            span += stack.peek()[1];
            stack.pop();
        }
        stack.push(new int[]{price, span});
        return span;
    }
}
Python
class StockSpanner:

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

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Complexity

  • ⏰ Time complexity: O(n) in the amortized case, where n is the number of price updates. Each price is pushed and popped from the stack at most once. So 2 * N times stack operations and N times calls.
  • 🧺 Space complexity: O(n), where n is the number of price updates, for storing prices and spans in the stack.

Dry Run