Stock Span Problem

Problem Description

The stock span problem requires designing an algorithm to calculate the span of a stock's price for each day. The span for a particular day is defined as the maximum number of consecutive days (including the current day and going backward) for which the stock's price was less than or equal to the price on the current day.

1. Brute Force Solution

A straightforward approach is to iterate backward from the current day for each new price, counting how many consecutive days have prices less than or equal to the current day's price.

Algorithm

1. Store all prices in an array.
2. For each new price:
   • Append the price to the array.
   • Initialize span = 1.
   • Iterate backward from the previous day:
     • If the price on that day is less than or equal to the current day's price, increment span.
     • Otherwise, break the loop.
   • Return span.

Code (Python)

class StockSpanner:
    def __init__(self):
        self.prices = []

    def next(self, price: int) -> int:
        self.prices.append(price)
        span = 1
        for i in range(len(self.prices) - 2, -1, -1):
            if self.prices[i] <= price:
                span += 1
            else:
                break
        return span

Time Complexity

• O(N^2) in the worst case, where N is the number of days. This happens when prices are non-decreasing.

Space Complexity

• O(N) to store the prices.

2. Optimal Solution Using a Stack

A more efficient solution uses a stack to keep track of previous prices and their spans. The stack stores pairs of (price, span). When a new price comes in, we compare it with the prices on the stack. If the stack's top price is less than or equal to the current price, we pop it and add its span to the current span. We continue this until the stack is empty or the stack's top price is greater than the current price.

Algorithm

1. Initialize a stack to store (price, span) pairs.
2. For each new price:
   • Initialize span = 1.
   • While the stack is not empty and the stack's top price is less than or equal to the current price:
     • Pop the stack's top element and add its span to the current span.
   • Push the current (price, span) onto the stack.
   • Return span.

Code (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

Time Complexity

• O(N) in total, where N is the number of days. Each price is pushed and popped from the stack at most once.

Space Complexity

• O(N) to store the stack.

3. Edge Cases

• Empty Input Stream: The algorithm should work correctly even if next() is called immediately without any prior calls.
• Monotonically Increasing Prices: The stack will keep popping elements, resulting in larger spans.
• Monotonically Decreasing Prices: Each span will be 1, and the stack will grow linearly.

Summary

The stack-based solution provides an optimal approach to the stock span problem with linear time complexity. It efficiently computes the span for each day by keeping track of relevant previous prices and their spans, making it suitable for real-time data analysis.