Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

901. Online Stock Span - Leetcode Solution

Code Implementation

class StockSpanner:
    def __init__(self):
        self.stack = []  # Each element is (price, span)

    def next(self, price: int) -> int:
        span = 1
        # Pop prices less than or equal to current and accumulate their spans
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span
      
class StockSpanner {
public:
    StockSpanner() {}
    
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.back().first <= price) {
            span += st.back().second;
            st.pop_back();
        }
        st.emplace_back(price, span);
        return span;
    }
private:
    std::vector<std::pair<int, int>> st;
};
      
class StockSpanner {
    private Stack<int[]> stack;

    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}
      
var StockSpanner = function() {
    this.stack = [];
};

StockSpanner.prototype.next = function(price) {
    let span = 1;
    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
        span += this.stack.pop()[1];
    }
    this.stack.push([price, span]);
    return span;
};

Problem Description

The Online Stock Span problem requires you to design a data structure that processes a stream of daily stock prices and, for each price, returns the "span" of that price. The span of a stock's price on a certain day is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price. You must implement a class (usually named StockSpanner) with two methods:
  • StockSpanner(): Initializes the object.
  • next(price): Given the price of the stock for today, returns the span of today's price.
Each call to next represents a new day. The input is a sequence of prices, and you must return the span for each price as it arrives. There is only one valid span for each price, and previous prices cannot be reused or revisited except for calculation.

Thought Process

At first glance, it might seem that for each new price, we need to look back through all previous prices until we find one greater than today's price, counting the number of days as we go. This brute-force approach would check, for every day, all previous days, leading to a lot of repeated work. However, this is inefficient, especially as the number of prices grows. The key is to recognize that we don’t need to examine every previous price individually. If a previous price is less than or equal to today's price, then its span can be "merged" with today's span. This observation suggests that we can use a stack to keep track of prices and their spans, efficiently combining spans as we process each new price. This is similar to the "Next Greater Element" pattern, but instead of just finding the next larger value, we also accumulate the span counts as we pop from the stack.

Solution Approach

To solve the problem efficiently, we use a stack-based approach:
  1. We maintain a stack where each element is a pair: (price, span). The stack is strictly decreasing by price from bottom to top.
  2. For each new price:
    • Initialize the span to 1 (today itself counts).
    • While the stack is not empty and the top price is less than or equal to today's price:
      • Pop the top element off the stack and add its span to the current span.
    • Push (price, span) onto the stack.
    • Return the span.
  3. This way, each price is pushed and popped at most once, guaranteeing an efficient solution.
This approach is optimal because it avoids redundant checks by "compressing" sequences of lower prices into a single span, leveraging the stack for fast updates and queries.

Example Walkthrough

Let's walk through an example with the input prices: [100, 80, 60, 70, 60, 75, 85].
  • Day 1, price=100: Stack is empty. Span=1. Stack: [(100,1)]
  • Day 2, price=80: 80 < 100, so Span=1. Stack: [(100,1), (80,1)]
  • Day 3, price=60: 60 < 80, so Span=1. Stack: [(100,1), (80,1), (60,1)]
  • Day 4, price=70: 70 > 60, pop (60,1), Span=2. 70 < 80, stop. Stack: [(100,1), (80,1), (70,2)]
  • Day 5, price=60: 60 < 70, so Span=1. Stack: [(100,1), (80,1), (70,2), (60,1)]
  • Day 6, price=75: 75 > 60, pop (60,1), Span=2. 75 > 70, pop (70,2), Span=4. 75 < 80, stop. Stack: [(100,1), (80,1), (75,4)]
  • Day 7, price=85: 85 > 75, pop (75,4), Span=5. 85 > 80, pop (80,1), Span=6. 85 < 100, stop. Stack: [(100,1), (85,6)]
The returned spans are: [1, 1, 1, 2, 1, 4, 6]. This shows how the stack efficiently tracks and compresses spans.

Time and Space Complexity

  • Brute-force approach: For each price, we might look back at all previous prices, so the time complexity is O(n^2) for n prices. Space is O(n) for storing prices.
  • Optimized stack approach: Each price is pushed and popped at most once, so the total number of stack operations is at most 2n. Thus, time complexity is O(n) for n calls to next. Space complexity is O(n) for the stack.

Summary

The Online Stock Span problem is efficiently solved using a stack to track prices and their spans. By merging spans of consecutive lower prices, we avoid redundant work and achieve linear time complexity. The stack-based approach is elegant because it leverages the structure of the problem, ensuring each price is processed in constant amortized time, making it suitable for large input streams. The key insight is to "compress" the history of prices using spans, allowing fast updates and queries.