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.

• 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

---

✅ 1. Problem Explanation (In Simple Terms)

You're designing a system that processes a daily stream of stock prices, one day at a time.

Each day, for the current price, you need to return the stock span:

The span of the stock's price today is the number of consecutive days (including today) the price has been less than or equal to today's price.

📘 For example:

Input: [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]

Why?

• Day 6 (price 75): previous prices <= 75 are [60, 70, 60, 80] → 4 days

---

💡 2. Key Insights

1. Naive Approach:

   • For each new price, walk backward and count days where price ≤ current.

   • ❌ Too slow → O(n²)

2. Optimized Approach (Monotonic Stack):

   • Maintain a stack of [price, span]

   • For each new price:

     • Pop from the stack while top.price ≤ current

     • Accumulate span from popped items

   • Push [current price, accumulated span + 1] onto stack

3. This ensures:

   • We always have a strictly decreasing stack of prices

   • Each price is pushed/popped once → O(n) total

---

🧠 3. Steps to Solve

1. Initialize a stack [] to store [price, span] pairs

2. For each new price:

   • Set span = 1

   • While stack not empty and stack.top().price ≤ current:

     • Pop from stack and add its span to current

   • Push [price, span] to stack

   • Return the span

---

✅ 4. JavaScript Code (Clean & Efficient)

class StockSpanner {
  constructor() {
    // Stack holds [price, span]
    this.stack = [];
  }

  /**
   * @param {number} price
   * @return {number}
   */
  next(price) {
    let span = 1;

    // Accumulate spans for prices <= current
    while (
      this.stack.length > 0 &&
      this.stack[this.stack.length - 1][0] <= price
    ) {
      span += this.stack.pop()[1];
    }

    this.stack.push([price, span]);
    return span;
  }
}

Usage:

const stock = new StockSpanner();
console.log(stock.next(100)); // 1
console.log(stock.next(80));  // 1
console.log(stock.next(60));  // 1
console.log(stock.next(70));  // 2
console.log(stock.next(60));  // 1
console.log(stock.next(75));  // 4
console.log(stock.next(85));  // 6

---

🔍 5. Dry Run Example

Input: [100, 80, 60, 70, 60, 75, 85]

✅ Final Output: [1, 1, 1, 2, 1, 4, 6]

---

⏱️ 6. Time & Space Complexity

Let n be the number of calls to next(price).

• Time (per call): amortized O(1) (each element is pushed and popped once)

• Total Time: O(n)

• Space: O(n) for stack in worst case (strictly decreasing sequence)

---

✅ Final Verdict

• This is a classic monotonic stack pattern

• Efficient for streaming data

• Real-world use case: browser price tickers, charts, analytics dashboards

Let me know if you want:

• A follow-up: support rollback of prices

• Real-time visualization chart using spans

• Or convert this into a TypeScript class with typings