Online Stock Span

---

Intuition

Brute Force

• For each stock, check the ones before it until you find a previous stock not less than or equal to the current one.

Optimization

• We can achieve $O(N)$ if we notice the following:
  • The previously calculated span denotes the number of elements we can skip
  • That is, if a previous stock is less than or equal to the current one, the current stock must be greater than or equal to all the stocks that stock is greater than equal to!
  • And that amount to skip is the same as the span for that previous stock.
• We repeat this, concluding only if there are no stocks previous to the current one.

Note

I start at i = len(stack) - 1, since while I am at the first stock, there are no previous stocks/spans to compare to.

Question

Why do you additionally need to keep track of the prices?

Complexity

Runtime

$O(N)$

• Each element can be only popped off once.
• There are 2 cases:

  • = previous

    • Skip previously computed
  • < previous
    • We stop here
• Note that this is the ammortized cost. In the worst case, it will still be $O(N^2)$.

Space

$O(N)$

Code

Just Stack

class StockSpanner:
 
    def __init__(self):
        self.stack = []
    
    def next(self, price: int) -> int:
        count = 1
        while self.stack and price >= self.stack[-1][0]:
            count += self.stack[-1][1]
            self.stack.pop()
        
        self.stack.append((price, count))
        return count
        
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

Keeping Count

class StockSpanner:
 
    def __init__(self):
        self.prices = []
        self.stack = []
        
    def next(self, price: int) -> int:
        i = len(self.prices) - 1
        count = 1
        while i >= 0 and price >= self.prices[i]:
            count += self.stack[i]
            i -= self.stack[i]
 
        self.prices.append(price)
        self.stack.append(count)
        return count
        
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

Notes

Cards

START Basic Front: Online Stock Span Back:

END

---

References

• Online Stock Span