Online Stock Span

Description

901. Online Stock Span

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.

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); // returns 1
stockSpanner.next(80);  // returns 1
stockSpanner.next(60);  // returns 1
stockSpanner.next(70);  // returns 2
stockSpanner.next(60);  // returns 1
stockSpanner.next(75);  // returns 4 (prices: 60, 70, 60, 75 are all <= 75)
stockSpanner.next(85);  // returns 6 (prices: 80, 60, 70, 60, 75, 85 are all <= 85)
 

Constraints:

• $1\le \text{price}\le 10^5$
• At most $10^4$ calls will be made to next.

---

Approach 1: Brute Force ($O(N)$ Time per next() Call)

Intuition

Store all daily stock prices sequentially in a list. Every time next(price) is called, add the price to the list and iterate backward from the end to count how many consecutive preceding prices are less than or equal to price.

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;
 
        // Iterate backwards from today's price
        for (int i = prices.size() - 1; i >= 0; i--) {
            if (prices.get(i) <= price) {
                span++;
            } else {
                break;
            }
        }
 
        return span;
    }
}
 

Complexity

• Time Complexity: $O(N)$ per next() call in the worst case (e.g., non-decreasing prices), resulting in $O(N^2)$ time over $N$ queries.
• Space Complexity: $O(N)$ to store all incoming prices.

---

Approach 2: Monotonic Stack (Optimal — Amortized $O(1)$ Time)

Intuition

Avoid scanning smaller values individually by maintaining a monotonic decreasing stack that stores pairs of [price, span].

When a new price arrives:

1. Start with span = 1 for the current day.
2. While the top element on the stack has a price $\le$ current price, pop it off and add its accumulated span to the current span.
3. Push [price, span] onto the stack.

By “collapsing” smaller prices into a single span count, each element is pushed and popped at most once.

import java.util.ArrayDeque;
import java.util.Deque;
 
class StockSpanner {
    // Stack stores element pairs: [price, span]
    private Deque<int[]> stack;
 
    public StockSpanner() {
        stack = new ArrayDeque<>();
    }
 
    public int next(int price) {
        int span = 1;
 
        // Collapse all previous prices that are <= today's price
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
 
        // Push today's price along with its total accumulated span
        stack.push(new int[]{price, span});
 
        return span;
    }
}
 

Complexity

• Time Complexity: Amortized $O(1)$ per next() call. Across $N$ calls, every price entry is pushed once and popped at most once, giving $O(N)$ overall time.
• Space Complexity: $O(N)$ worst-case space to hold elements in the stack when prices are strictly decreasing.

---

Easy Memory Rule

“Store [price, span] in a Monotonic Decreasing Stack. When today’s price is higher, pop the smaller items and accumulate their spans into today’s span.”

1. Were we always using Deque for Monotonic Stack?

Yes, in standard Java practice, Deque (specifically ArrayDeque) is the recommended way to implement any Stack, including monotonic stacks.

While Java has a legacy Stack class (java.util.Stack), it is outdated and avoided for two main reasons:

1. Performance: Stack inherits from Vector, meaning every operation is synchronized (has lock overhead), making it slower.
2. Design Flaw: Because it extends Vector, you can access elements by random index (e.g., stack.get(2)), which violates the fundamental rules of a Stack data structure.

ArrayDeque is unsynchronized, faster, and memory-efficient.

---

2. What does push() actually mean on a Deque?

Because a Deque has two ends (FRONT and BACK), Java explicitly defines push(), pop(), and peek() to operate strictly on the FRONT (Head) of the Deque.

When you use Deque as a Stack:
$\text{[ FRONT / HEAD ] }⟵\text{All Stack operations happen here!}\text{ [ BACK / TAIL ]}$

Stack Method	Exact Deque Equivalent	What It Does
stack.push(x)	addFirst(x)	Inserts x at the FRONT
stack.pop()	removeFirst()	Removes and returns the item at the FRONT
stack.peek()	peekFirst()	Reads the item at the FRONT without removing it

---

Mental Model: Stack vs. Sliding Window Deque

• When using Deque as a STACK (LIFO): You only touch the FRONT using push(), pop(), and peek(). The back is completely untouched.
• When using Deque for SLIDING WINDOW MAX: You use BOTH ENDS explicitly (offerLast, pollLast, peekFirst) because you need to add/remove elements from both sides.