# Online Stock Span
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/online-stock-span)
Canonical: https://scaleengineer.com/dsa/problems/online-stock-span
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Stack, Monotonic Stack
**Companies:** [INDmoney](https://scaleengineer.com/companies/indmoney)
---
## Problem
Design an algorithm that collects daily price quotes for some stock and returns **the span** of that stock's price for the current day.

The **span** of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

* For example, if the prices of the stock in the last four days is `[7,2,1,2]` and the price of the stock today is `2`, then the span of today is `4` because starting from today, the price of the stock was less than or equal `2` for `4` consecutive days.
* Also, if the prices of the stock in the last four days is `[7,34,1,2]` and the price of the stock today is `8`, then the span of today is `3` because starting from today, the price of the stock was less than or equal `8` for `3` consecutive days.

Implement the `StockSpanner` class:

* `StockSpanner()` Initializes the object of the class.
* `int next(int price)` Returns the **span** of the stock's price given that today's price is `price`.

**Example 1:**

**Input**
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
**Output**
[null, 1, 1, 1, 2, 1, 4, 6]

**Explanation**
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

**Constraints:**

* `1 <= price <= 105`
* At most `104` calls will be made to `next`.

# Approaches
## Brute Force with List
This approach involves storing all the historical prices in a list. For each new price, we iterate backward through the list, counting how many consecutive days (including the current day) have a price less than or equal to the current day's price.
**Time:** O(N) for each call to `next`, where N is the number of calls made so far. In the worst case (e.g., an increasing sequence of prices), the loop will run N times for the N-th call. The total time complexity for M calls is O(M^2). · **Space:** O(N), where N is the number of calls made to `next`. We need to store all N prices in the list.
**Pros:** Simple to understand and implement.; Requires only a basic list data structure.
**Cons:** Inefficient for a large number of calls. The time per call grows linearly with the number of prices seen, leading to a quadratic total time complexity (`O(N^2)` for `N` calls), which can be too slow for the given constraints.
### Explanation
We maintain a `java.util.ArrayList` to store the sequence of prices received so far. The `StockSpanner` constructor initializes this list. In the `next(int price)` method, the new `price` is added to the end of the list. Then, we start a loop from the end of the list, moving backward. We count how many consecutive prices are less than or equal to the current day's price. The loop terminates as soon as we find a price that is greater than the current `price`, or when we have traversed the entire list. The final count is the span for the current day.

```java
import java.util.ArrayList;
import java.util.List;

class StockSpanner {
    private List<Integer> prices;

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

    public int next(int price) {
        prices.add(price);
        int span = 0;
        for (int i = prices.size() - 1; i >= 0; i--) {
            if (prices.get(i) <= price) {
                span++;
            } else {
                break;
            }
        }
        return span;
    }
}
```
### Algorithm
- 1. Initialize an empty list `prices` in the constructor.
- 2. In the `next(price)` method:
- 3. Add the new `price` to the `prices` list.
- 4. Initialize a counter `span` to 0.
- 5. Iterate backward from the end of the list (from index `prices.size() - 1` down to `0`).
- 6. For each price encountered, if it is less than or equal to the current `price`, increment `span`.
- 7. If a price is found that is greater than the current `price`, stop the iteration and break the loop.
- 8. Return the final `span` value.

## Optimized Approach using a Monotonic Stack
This approach uses a monotonic stack to efficiently calculate the span. Instead of re-scanning all previous prices, we maintain a stack of pairs, where each pair consists of a price and its calculated span. The stack is kept in a monotonically decreasing order of prices (from bottom to top). This allows us to "skip" over consecutive days with smaller prices in constant time on average.
**Time:** Amortized O(1) for each call to `next`. While a single call can take up to O(N) time, each element is pushed and popped from the stack at most once over the entire sequence of N calls. Thus, the total time for N calls is O(N). · **Space:** O(N), where N is the number of calls made. In the worst case (a strictly decreasing sequence of prices), the stack will store an entry for each price.
**Pros:** Highly efficient, with amortized constant time per operation.; Effectively handles large inputs without performance degradation.; Scales well as the number of calls increases.
**Cons:** Slightly more complex to conceptualize compared to the brute-force approach.; The space complexity is O(N) in the worst case, same as the brute-force approach.
### Explanation
The core idea is that the span of the current price is `1` (for the current day) plus the sum of the spans of all preceding consecutive days with prices less than or equal to the current price. We use a stack to store pairs of `[price, span]`. The stack will always maintain prices in a decreasing order.

When `next(int price)` is called:
1. We initialize the current span to `1`.
2. We look at the top of the stack. As long as the stack is not empty and the price at the top is less than or equal to the current `price`, we pop from the stack.
3. For each element popped, we add its span to our current span. This is the key optimization: instead of counting one by one, we add the entire span of the smaller preceding element, effectively jumping over a block of days.
4. After the loop, we have the final span for the current price.
5. We then push the pair of `(current price, calculated span)` onto the stack to be used for future calculations. This maintains the monotonic property of the stack.

```java
import java.util.Stack;

class StockSpanner {
    private Stack<int[]> stack;

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

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}
```
### Algorithm
- 1. Initialize an empty stack `stack` in the constructor. The stack will store pairs of `[price, span]`.
- 2. In the `next(price)` method:
- 3. Initialize `currentSpan = 1` (for the current day's price).
- 4. While the `stack` is not empty and the price of the element at the top of the stack (`stack.peek()[0]`) is less than or equal to the current `price`:
- 5. Pop the element from the stack. Add its stored span (`popped[1]`) to `currentSpan`.
- 6. After the loop finishes, push a new pair `[price, currentSpan]` onto the stack.
- 7. Return `currentSpan`.

# Solutions
### Java

```java
class StockSpanner { private Deque < int []> stk = new ArrayDeque <>(); public StockSpanner () { } public int next ( int price ) { int cnt = 1 ; while (! stk . isEmpty () && stk . peek ()[ 0 ] <= price ) { cnt += stk . pop ()[ 1 ]; } stk . push ( new int [] { price , cnt }); return cnt ; } } /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner obj = new StockSpanner(); * int param_1 = obj.next(price); */
```

### CPP

```cpp
class StockSpanner { public: StockSpanner () { } int next ( int price ) { int cnt = 1 ; while ( ! stk . empty () && stk . top (). first <= price ) { cnt += stk . top (). second ; stk . pop (); } stk . emplace ( price , cnt ); return cnt ; } private: stack < pair < int , int >> stk ; }; /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner* obj = new StockSpanner(); * int param_1 = obj->next(price); */
```

### Python

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