901. Online Stock Span

MediumStackDesignData StreamMonotonic Stack
Leetcode Link

Problem Description

The objective is to design an algorithm that can process a series of daily stock prices and determine the stock's price span for any given day. The price span is defined as the maximum number of consecutive days (counting backwards from the current day) during which the stock's price was less than or equal to that day's price. For example, if the sequence of stock prices over the last few days was [6, 5, 4, 5] and the price today is 5, the span would be 2, as the price today and the day before were 5 or less.

The main challenge is to efficiently calculate the span while handling a potentially large stream of daily prices. A naive approach that checks all previous stock prices daily would not be efficient enough.

Intuition

To find a span efficiently, we use a monotonic stack. This is a fundamental data structure that is useful when we want to find the next element greater or smaller in an array. In this case, we are looking for the first price greater than the current price as we move backward in time.

The monotonic stack maintains a decreasing sequence of prices along with their corresponding spans. When a new price arrives, we compare it with the price at the top of the stack. If the new price is greater, we pop elements from the stack, accumulating their spans as we go, until we find a higher price in the stack or the stack is empty.

We then push the current price and the accumulated span onto the stack. The accumulated span is the answer we are looking for - it tells us how far back we can go with prices less than or equal to the current price.

This approach is efficient because each price is processed and pushed to the stack exactly once, and popped at most once. This gives the solution a time complexity that is average-case O(1) for each call to next, which is much more efficient than the naive approach.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The StockSpanner class is implemented using a monotonic stack pattern. This pattern is particularly useful for problems where we need to know the nearest element that is greater or smaller than the current element. In this case, our stack stores pairs of the form (price, cnt) where price is the stock price and cnt is the span of the stock for that price.

The stack is maintained in a way that the prices are monotonically decreasing from the bottom to the top. This means that when we consider a new stock price, we can repeatedly compare it with the elements from the top of the stack. If the new stock price is higher than the price at the top of the stack, we pop the stack and add the span (cnt) of that popped price to a running count. This process continues until we find a price in the stack that is greater than the current price or the stack becomes empty.

Here is how the implementation is performed step-by-step:

  • When next(price) is called, we set a variable cnt to 1. This cnt will accumulate the span of days for the current price.
  • We then enter a loop that keeps running as long as there is an element in the stack and the top element's price is less than or equal to the current price.
  • Inside the loop, we pop the top element from the stack and add its span (second element of the pair) to cnt.
  • After breaking out of the loop (either by finding a larger price or emptying the stack), we push the current price and accumulated span (cnt) as a pair onto the stack.
  • The next function then returns the accumulated cnt, which represents the span of the stock price for the given day.

Each next operation runs in O(1) average time complexity because even though we have a while loop inside the function, each element is pushed and popped from the stack at most once due to the property of a monotonic stack.

This clever use of a monotonic stack provides a time-efficient solution to calculating the spans, avoiding the need to traverse the entire list of previous stock prices for every call. As a result, the algorithm scales well with a large number of next operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume the stock prices over the past few days were [100, 80, 60, 70, 60, 75, 85]. We will walk through the sequence of next() operations with these prices and discuss how the StockSpanner class calculates the span for each day.

  1. next(100): The stack is initially empty, so the span for the first price (100) is 1 (day). We push (100, 1) onto the stack.

    Stack: [(100, 1)]

  2. next(80): 80 is less than 100, so the span is also 1. We push (80, 1) onto the stack.

    Stack: [(100, 1), (80, 1)]

  3. next(60): Similarly, 60 is less than 80, so the span is again 1. Push (60, 1) onto the stack.

    Stack: [(100, 1), (80, 1), (60, 1)]

  4. next(70): Now 70 is greater than 60, so we start popping from the stack. We pop (60, 1) since 60 is less than 70, and we accumulate the span, so cnt becomes 2. The top is now 80 which is greater than 70, so we stop and push (70, 2) onto the stack.

    Stack: [(100, 1), (80, 1), (70, 2)]

  5. next(60): The incoming price is 60 which is less than 70, so span is 1. Push (60, 1) onto the stack.

    Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]

  6. next(75): For incoming price 75, we pop (60, 1) and (70, 2) because those are smaller than 75 and accumulate their spans to cnt which now becomes 4. Now the top is 80 which is greater, so we stop and push (75, 4) onto the stack.

    Stack: [(100, 1), (80, 1), (75, 4)]

  7. next(85): For incoming price 85, we first pop (75, 4) as it is smaller and add its span to cnt making cnt 5. Next, we pop (80, 1) and add its span, so cnt is now 6. Now the top is 100 which is greater, so we push (85, 6) onto the stack.

    Stack: [(100, 1), (85, 6)]

Through the sequence of next() operations, we determined the spans without having to loop through all previous stock prices every time. The output sequence of spans would be [1, 1, 1, 2, 1, 4, 6] for the respective stock prices. This demonstrates the efficiency of the monotonic stack in calculating the price spans.

Solution Implementation

1class StockSpanner:
2    def __init__(self):
3        self.stack = []  # This stack will keep track of stock prices and their spans
4
5    def next(self, price: int) -> int:
6        # The count starts at 1, since the span of at least the current day is included
7        span_count = 1
8        # We pop prices from the stack if they are less than or equal to the current price.
9        # When a lower price is encountered, its span is added to the count.
10        while self.stack and self.stack[-1][0] <= price:
11            span_count += self.stack.pop()[1]
12        # Once all smaller (or equal) prices are popped, we append the current price and its calculated span.
13        self.stack.append((price, span_count))
14        return span_count
15
16# Example Usage:
17# obj = StockSpanner()
18# span = obj.next(price)
19
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4class StockSpanner {
5    // Stack to keep track of stock prices and span counts
6    // Each stack element is an array with the first element being the stock price
7    // and the second being the span count for that price
8    private Deque<int[]> stack = new ArrayDeque<>();
9
10    // Constructor for StockSpanner
11    public StockSpanner() {
12    }
13
14    // This method is called for every new stock price and returns the span count
15    // The span count is the number of consecutive days the stock price has been
16    // less than or equal to the current day's price, including the current day
17    public int next(int price) {
18        // Start the count as 1 for the current day
19        int count = 1;
20      
21        // Continue popping elements from the stack when the current price is greater
22        // than the price at the stack's top and accumulate the span counts
23        while (!stack.isEmpty() && stack.peek()[0] <= price) {
24            count += stack.pop()[1];
25        }
26      
27        // Push the current price along with its span count onto the stack
28        stack.push(new int[] {price, count});
29      
30        // Return the computed span count for the current price
31        return count;
32    }
33}
34
35/**
36 * The following "how to use" example is not part of the class itself and serves only as an illustration.
37 * 
38 * How to use:
39 * StockSpanner stockSpanner = new StockSpanner();
40 * int spanCount = stockSpanner.next(price);
41 */
42
1#include <stack>
2using namespace std;
3
4class StockSpanner {
5public:
6    StockSpanner() {
7        // Constructor, no initialization needed since the stack is empty initially
8    }
9
10    // Processes a new price, returning the span of that price
11    int next(int price) {
12        int span = 1; // Span always starts at least at 1 (for the current day)
13
14        // Continue popping from the stack while the stack is not empty and
15        // the price at the top of the stack is less than or equal to the current price
16        while (!pricesAndSpans.empty() && pricesAndSpans.top().first <= price) {
17            span += pricesAndSpans.top().second; // Add the span of the price at the top
18            pricesAndSpans.pop(); // Remove the price and its span now that it's processed
19        }
20
21        // Push current price and its calculated span onto the stack
22        pricesAndSpans.emplace(price, span);
23
24        // Return the span of the current price
25        return span;
26    }
27
28private:
29    // A stack that stores pairs of price and corresponding span
30    stack<pair<int, int>> pricesAndSpans;
31};
32
33/**
34 * Your StockSpanner object will be instantiated and called as such:
35 * StockSpanner* obj = new StockSpanner();
36 * int param_1 = obj->next(price);
37 */
38
1// Initialize an empty stack to keep track of stock prices and spans.
2let stack: number[][] = [];
3
4/**
5 * Processes the next price.
6 * 
7 * @param price - The current day's stock price.
8 * @returns The span (number of consecutive days) of the stock price 
9 * ending with the current day for which the price is less than or equal
10 * to the current day's price.
11 */
12function next(price: number): number {
13    // Start the current span at 1 (itself)
14    let span = 1;
15
16    // If the stack is not empty and the top stack price is less than or equal 
17    // to the current price, keep popping from the stack and increment the span
18    // by the span of the popped prices as their span becomes part of the current 
19    // span since our price is greater than those prices.
20    while (stack.length && stack[stack.length - 1][0] <= price) {
21        span += stack.pop()[1];
22    }
23
24    // Push the current price and its calculated span into the stack.
25    stack.push([price, span]);
26
27    // Return the span for the current price.
28    return span;
29}
30
31// Now functions next can be called globally with the current day's price
32// and will process the stock price span as per the described logic.
33// For example:
34// var spanToday = next(100);
35// This will calculate the span for the stock price 100.
36
Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

Time Complexity

The time complexity of the StockSpanner class operations are as follows:

  • __init__: The constructor has a time complexity of O(1) as it only initializes an empty list.

  • next: The time complexity of this function is amortized O(1). Although at first glance it seems to be O(n) per call (because of the while loop), it's important to note that each element is added once and removed at most once. Therefore, over n calls, there will be at most n additions and n removals, leading to an average complexity of O(1) per call. The reference answer states the time complexity as O(n), which could be referring to the worst-case scenario for a single call, but amortized over multiple calls, it's constant.

Space Complexity

The space complexity of the StockSpanner class is O(n), where n is the number of prices processed. In the worst case, if the prices are strictly decreasing, all prices will be stored in the stack self.stk.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Median of Data Stream

Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«