Online Stock Span – 901. LeetCode

The “Online Stock Span” problem involves calculating the stock span, which the number of consecutive days (including today) a stock’s price was less than or equal to its current price. For example, if the stock price today is higher than the last three days, the span is four. It’s like finding out how long the current stock price has been “the highest” in a sequence of prices.

Brute Force Approach

class StockSpanner {
    private List<Integer> prices;

    public StockSpanner() {
        prices = new ArrayList<>();
    }

    public int next(int price) {
        prices.add(price);
        int span = 1; // At least today's price counts.
        for (int i = prices.size() - 2; i >= 0; i--) {
            if (prices.get(i) <= price) {
                span++;
            } else {
                break;
            }
        }
        return span;
    }
}

• The code stores all prices in a list and calculates the span by iterating backward through the list, comparing each previous price to the current one.
• For each new price:
  • It adds the price to the list.
  • Iterates backward from the current price, counting how many consecutive previous prices are less than or equal to the current price.

Optimal Algorithm and Data Structure

Algorithm and Data Structure Choice

The Monotonic Stack data structure is well-suited for this problem. A monotonic stack keeps track of indices of prices in a way that the stack’s elements are ordered. This avoids redundant comparisons and gives the span in constant time for each price.

The key observation is that to find the span of a price, you only need to know the closest price that is greater than it. A monotonic stack efficiently tracks this:

• Stack stores indices of prices where the prices are strictly decreasing from top to bottom.

• If a price is greater than or equal to the price represented by the top of the stack, we pop the stack (remove those indices).

• The span is then calculated as the difference between the current index and the new top of the stack.

Algorithm Steps

1. Use a stack to store pairs of price and span.

2. For a new price:

• Pop elements from the stack while the price at the top of the stack is less than or equal to the current price.

• Add the span of all popped elements to the current span.

3. Push the new price and span onto the stack.

4. Return the span.

class StockSpanner {
    private Stack<int[]> stack; // Stores pairs of price and span.

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

    public int next(int price) {
        int span = 1;
        // Combine spans of all smaller prices.
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        // Push the current price and its span.
        stack.push(new int[] {price, span});
        return span;
    }
}

Line By Line Explanation

Step 1: Setting Up The Constructor

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

• The stack will store all the prices and their spans in an efficient way so we can retrieve or update them as needed. it’s the foundation of the system.

Step 2: Initialize Span To 1

public int next(int price) {
    int span = 1;

• Every price has at least 1 day of span, so initialize span to 1.

Step 3: Checking Past Prices

while (!stack.isEmpty() && stack.peek()[0] <= price) {
    span += stack.pop()[1];
}

• Check the stack
• If the price at the top of the stack is less than or equal to current price.
  • Add the span of that smaller price to today’s span.
  • Remove that price from the stack (pop it) because it’s no longer relevant for future comparisons.

Step 4: Adding The Current Stock

stack.push(new int[] {price, span});

• Stores the current price and its span for future comparisons.
• This will help calculate the spans for future prices.

Step 5: Return

return span;

• Returns the calculated span for the current price.

Why This Code

The monotonic stack algorithm optimizes the brute-force solution by avoiding redundant comparisons, making it both faster and more space-efficient. It demonstrates the power of understanding problem characteristics (e.g., finding nearest greater elements) and using patterns like monotonic stacks for efficient solutions.