Time Complexity Analysis

The time complexity for a single call to next is $O(N)$, where $N$ is the number of calls made so far. In the worst-case scenario (e.g., a strictly decreasing sequence of prices like 100, 99, 98...), the algorithm scans only one element. However, if the prices are increasing, or we have a sequence like 50, 50, 50, ... 100, the algorithm rescans the entire history.

Over $N$ calls, the total time complexity becomes $O(N^2)$.

Why It Fails

The constraints specify up to $10^4$ calls. While $O(N^2)$ might pass for $N=10^4$ in some relaxed environments (approx $10^8$ operations), it is inefficient and prone to Time Limit Exceeded (TLE) errors on stricter platforms or larger test cases. More importantly, in an interview context, an $O(N^2)$ solution for a stream processing problem is considered suboptimal.

Core Insight for Online Stock Span

The key intuition is that if a past price is smaller than or equal to today's price, it will never be the "stopping point" (the Previous Greater Element) for any future price.

Consider a sequence of prices: [60, 70, 80].

• When 60 comes in, its span is 1.
• When 70 comes in, it is greater than 60. Any future price greater than 70 will automatically be greater than 60. Therefore, 60 becomes irrelevant as an individual data point; its weight (span of 1) is absorbed into 70.
• When 80 comes in, it absorbs 70 (which already includes 60).

We can compress the history. Instead of storing every individual price, we store "blocks" or "intervals" of prices in a stack. Each element in the stack is a pair: {price, span}. The stack maintains the invariant that prices are strictly decreasing from bottom to top.

Visual Description: Imagine the prices as a skyline. A new building (current price) is constructed. If this new building is taller than the buildings immediately to its left, it "covers" or "hides" them. We collapse the hidden buildings into the new one, adding their widths (spans) to the new building's width. The stack represents the visible skyline of decreasing peaks that haven't been covered yet.

Execution Flow

Let's trace the algorithm with the input prices: [100, 80, 60, 70, 60, 75, 85].

1. Input: 100

   • Stack is empty.
   • Push (100, 1).
   • Return 1.
   • Stack: [(100, 1)]

2. Input: 80

   • Top is (100, 1). $100 > 80$. No merge.
   • Push (80, 1).
   • Return 1.
   • Stack: [(100, 1), (80, 1)]

3. Input: 60

   • Top is (80, 1). $80 > 60$. No merge.
   • Push (60, 1).
   • Return 1.
   • Stack: [(100, 1), (80, 1), (60, 1)]

4. Input: 70

   • Top is (60, 1). $60 \le 70$.
   • Merge: Pop (60, 1). Current span becomes $1 + 1 = 2$.
   • New Top is (80, 1). . Stop merging.

5. Input: 60

   • Top is (70, 2). $70 > 60$. No merge.
   • Push (60, 1).
   • Return 1.
   • Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]

6. Input: 75

   • Top is (60, 1). $60 \le 75$. Pop. Span: $1 + 1 = 2$.
   • New Top is (70, 2). $70\le 75$. Pop. Span: .

7. Input: 85

   • Top is (75, 4). $75 \le 85$. Pop. Span: $1 + 4 = 5$.
   • New Top is (80, 1). $80\le 85$. Pop. Span: .

Proof of Correctness

The correctness relies on the associative property of the span. The span of a price $P_i$ is $1 + \sum (\text{spans of all consecutive preceding prices } \le P_i)$.

When we pop an element $(P_{prev}, S_{prev})$ because $P_{prev} \le P_{curr}$, we are asserting that the $S_{prev}$ days covered by $P_{prev}$ are also smaller than $P_{curr}$. Since $P_{prev}$ was already the maximum of its own span range, and $P_{curr} \ge P_{prev}$, it follows that $P_{curr}$ is greater than or equal to all individual prices in that range. Thus, we can safely accumulate $S_{prev}$ into the current span. The stack invariant (strictly decreasing prices) ensures we efficiently find the nearest preceding price strictly greater than $P_{curr}$ without checking every single day.

Reference Implementation

C++ Solution for LeetCode 901

cpp
class StockSpanner {
private:
    // Pair stores {price, span}
    stack<pair<int, int>> st;

public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int span = 1;
        
        // Monotonic Stack: Pop elements that are less than or equal to current price
        // Accumulate their spans into the current span
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        
        // Push current price and its calculated span
        st.push({price, span});
        
        return span;
    }
};

Java Solution for LeetCode 901

java
import java.util.Stack;

class StockSpanner {
    // Stack stores int arrays where:
    // index 0 is the price
    // index 1 is the span
    private Stack<int[]> stack;

    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int span = 1;
        
        // Monotonic Stack: Pop elements that are less than or equal to current price
        // Accumulate their spans into the current span
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.peek()[1];
            stack.pop();
        }
        
        stack.push(new int[]{price, span});
        
        return span;
    }
}

Python Solution for LeetCode 901

python
class StockSpanner:

    def __init__(self):
        # Stack stores tuples of (price, span)
        self.stack = []

    def next(self, price: int) -> int:
        span = 1
        
        # Monotonic Stack: Pop elements that are less than or equal to current price
        # Accumulate their spans into the current span
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        
        self.stack.append((price, span))
        
        return span

Why do we store the span in the stack?

A common mistake is storing only the price in the stack. If you only store the price, when you pop a smaller price, you lose the information about how many days that price covered. You must aggregate the history as you pop.

Can we just store the index?

Yes, storing (price, index) is an alternative implementation of the same pattern. However, since this is an "online" problem (streaming data), calculating current_index - previous_greater_index requires maintaining a global index counter. Storing the span directly is often more intuitive for the specific requirement of "count consecutive days" and avoids index arithmetic errors.

What happens if the stack becomes empty?

If the stack becomes empty after popping, it means the current price is greater than all prices seen so far. The logic naturally handles this: the while loop terminates, and we push the current price with the accumulated span of the entire history plus one.