Problem Description

You need to design a class that tracks daily stock prices and calculates the "span" for each day's price.

The span of a stock price on a given day is defined as the maximum number of consecutive days (including the current day and going backward) where the stock price was less than or equal to the current day's price.

Let's understand with examples:

• If the last 4 days had prices [7, 2, 1, 2] and today's price is 2, the span is 4. This is because looking backward from today: 2 <= 2 (today), 1 <= 2 (1 day ago), 2 <= 2 (2 days ago), 2 <= 2 (3 days ago). All 4 consecutive days have prices ≤ 2.

• If the last 4 days had prices [7, 34, 1, 2] and today's price is 8, the span is 3. Looking backward: 8 <= 8 (today), 2 <= 8 (1 day ago), 1 <= 8 (2 days ago), but 34 > 8 (3 days ago). So only 3 consecutive days have prices ≤ 8.

You need to implement the StockSpanner class with:

• StockSpanner(): Initializes the object
• next(int price): Takes today's price and returns the span for that price

The key insight is that this problem can be solved efficiently using a monotonic stack. The stack maintains pairs of (price, span) in decreasing order of prices. When a new price comes in, we pop all elements with prices less than or equal to the current price, accumulating their spans. This accumulated span plus 1 (for the current day) gives us the final span for the current price.

Intuition

When we need to find the span for a given day's price, we're essentially asking: "How many consecutive previous days (including today) had prices less than or equal to today's price?"

The naive approach would be to store all prices and, for each new price, iterate backward counting days until we find a higher price. This would take O(n) time for each query in the worst case.

But here's the key observation: if we have a day with price p1 and span s1, and a later day comes with price p2 where p2 >= p1, then all the days covered by p1's span are automatically included in p2's span. We don't need to check those days individually again - we can directly add s1 to p2's span count.

This leads us to think about maintaining only the "significant" prices - those that could potentially stop a future price's span. These are prices that form a decreasing sequence when viewed from the most recent day backward.

Consider this sequence: [7, 2, 1, 3]. When price 3 arrives:

• We compare with 1: since 3 >= 1, we include its span
• We compare with 2: since 3 >= 2, we include its span too
• We compare with 7: since 3 < 7, we stop

After processing 3, we don't need to keep 1 and 2 anymore because any future price that's greater than 3 will automatically be greater than 1 and 2. The price 3 "blocks" them from being relevant to future calculations.

This pattern suggests using a stack where we maintain prices in decreasing order (from bottom to top). Each element stores both the price and its calculated span. When a new price arrives, we pop all smaller or equal prices, accumulating their spans, because all days they represent are now part of the current day's span.

Learn more about Stack, Data Stream and Monotonic Stack patterns.

Solution Approach

We implement the solution using a monotonic decreasing stack that stores pairs of (price, span).

Data Structure

• self.stk: A stack that maintains price-span pairs in decreasing order of prices (from bottom to top)

Algorithm for next(price)

1. Initialize span counter: Start with cnt = 1 to count the current day itself.

2. Process the stack: While the stack is not empty AND the price at the top of the stack is less than or equal to the current price:

   • Pop the top element (old_price, old_span) from the stack
   • Add old_span to our current cnt: cnt += self.stk.pop()[1]
   • This step consolidates all consecutive days with prices ≤ current price

3. Push current price: After processing, push (price, cnt) onto the stack. This pair represents:

   • The current price
   • The total span calculated (including all popped elements' spans)

4. Return the span: Return cnt as the span for the current day

Why This Works

The stack maintains a decreasing sequence of prices. Each element's span represents how many consecutive days (before encountering a higher price) that price dominated.

When a new price arrives:

• If it's higher than some stack elements, those elements' spans get absorbed into the new price's span
• The new price then "blocks" those removed prices from affecting future calculations
• If it's lower than the top of the stack, it simply gets added with span 1

Example Walkthrough

Let's trace through prices [100, 80, 60, 70, 60, 75, 85]:

• next(100): Stack empty, push (100, 1), return 1
• next(80): 80 < 100, push (80, 1), return 1
• next(60): 60 < 80, push (60, 1), return 1
• next(70): 70 >= 60, pop (60, 1), cnt = 1 + 1 = 2, push (70, 2), return 2
• next(60): 60 < 70, push (60, 1), return 1
• next(75): 75 >= 60, pop (60, 1), 75 >= 70, pop (70, 2), cnt = 1 + 1 + 2 = 4, push (75, 4), return 4
• next(85): 85 >= 75, pop (75, 4), 85 >= 80, pop (80, 1), cnt = 1 + 4 + 1 = 6, push (85, 6), return 6

Time and Space Complexity

• Time: O(1) amortized per operation. Each price is pushed and popped at most once.
• Space: O(n) in the worst case when prices are strictly decreasing.

Example Walkthrough

Let's walk through a simple example with prices [100, 80, 60, 70, 75] to see how the monotonic stack solution works.

Initial State: Stack is empty []

Day 1: price = 100

• Stack is empty, so no elements to pop
• cnt = 1 (just counting today)
• Push (100, 1) onto stack
• Stack: [(100, 1)]
• Return: 1

Day 2: price = 80

• Top of stack is (100, 1) where 100 > 80, so we don't pop anything
• cnt = 1 (just counting today)
• Push (80, 1) onto stack
• Stack: [(100, 1), (80, 1)]
• Return: 1

Day 3: price = 60

• Top of stack is (80, 1) where 80 > 60, so we don't pop anything
• cnt = 1 (just counting today)
• Push (60, 1) onto stack
• Stack: [(100, 1), (80, 1), (60, 1)]
• Return: 1

Day 4: price = 70

• Top of stack is (60, 1) where 60 <= 70, so we pop it
• Add its span to our count: cnt = 1 + 1 = 2
• Next top is (80, 1) where 80 > 70, so we stop popping
• Push (70, 2) onto stack (price 70 with span 2)
• Stack: [(100, 1), (80, 1), (70, 2)]
• Return: 2 (meaning prices on day 3 and day 4 are both ≤ 70)

Day 5: price = 75

• Top of stack is (70, 2) where 70 <= 75, so we pop it
• Add its span to our count: cnt = 1 + 2 = 3
• Next top is (80, 1) where 80 > 75, so we stop popping
• Push (75, 3) onto stack
• Stack: [(100, 1), (80, 1), (75, 3)]
• Return: 3 (meaning prices on days 3, 4, and 5 are all ≤ 75)

Notice how when we popped (70, 2) in the last step, we inherited its span of 2, which already accounted for days 3 and 4. This is the key efficiency: we don't need to look back at those individual days again because the span in our stack already captured that information.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) amortized, where n is the total number of times next(price) is called.

While a single call to next(price) might iterate through multiple elements in the stack (appearing to be O(n) worst case for that call), each element is pushed onto the stack exactly once and popped at most once throughout all operations. Therefore, across n calls to next(price), the total number of push and pop operations is at most 2n, giving us an amortized time complexity of O(1) per operation, and O(n) total for n operations.

Space Complexity: O(n), where n is the number of times next(price) is called.

In the worst case, when prices are in strictly increasing order, no elements are popped from the stack, and each call to next(price) adds one element to the stack. Therefore, the stack can grow to contain up to n elements, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Comparison Operator

Problem: Using strict inequality (<) instead of less than or equal to (<=) when comparing prices.

# WRONG - This will miss equal prices
while self.stack and self.stack[-1][0] < price:  # Should be <=
    previous_price, previous_span = self.stack.pop()
    span += previous_span

Why it's wrong: The span definition includes days where the price was equal to the current price, not just less than. If you use <, you'll incorrectly exclude days with the same price from the span calculation.

Solution: Always use <= for the comparison:

# CORRECT
while self.stack and self.stack[-1][0] <= price:
    previous_price, previous_span = self.stack.pop()
    span += previous_span

Pitfall 2: Forgetting to Accumulate Spans

Problem: Only counting the number of popped elements instead of accumulating their spans.

# WRONG - Only counts individual days, not accumulated spans
def next(self, price: int) -> int:
    span = 1
    while self.stack and self.stack[-1][0] <= price:
        self.stack.pop()
        span += 1  # Wrong! Should add the popped element's span
    self.stack.append((price, span))
    return span

Why it's wrong: Each element in the stack already has an accumulated span representing multiple days. By only adding 1 for each popped element, you're losing the information about the days that element represented.

Solution: Extract and add the span value from each popped element:

# CORRECT
while self.stack and self.stack[-1][0] <= price:
    previous_price, previous_span = self.stack.pop()
    span += previous_span  # Add the entire span, not just 1

Pitfall 3: Not Storing the Span with Each Price

Problem: Storing only prices in the stack without their corresponding spans.

# WRONG - Stack only stores prices
class StockSpanner:
    def __init__(self):
        self.stack = []  # Just storing prices
  
    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1] <= price:
            self.stack.pop()
            span += 1  # Can't know the actual span of popped element
        self.stack.append(price)  # Only pushing price
        return span

Why it's wrong: Without storing the span, you can't know how many days each popped price represented. This leads to incorrect span calculations when prices are popped.

Solution: Store tuples of (price, span) in the stack:

# CORRECT
self.stack.append((price, span))  # Store both price and its span