Solving “Online Stock Span” — Coding Interview Question

In this post, we will explore the pattern which can be used to solve the popular coding interview question ‘Online Stock Span’.

Problem Statement

Here is the problem statement provided on Leetcode:

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.

Solution

Let’s look at the naive solution first.

Brute Force Solution

The most straightforward approach is as follows:

1. Store all prices in a list.
2. For each new price, traverse the list backwards to count the days until you find a day with a higher price.

class StockSpanner {
    // List to store the prices
    List<Integer> prices;

    // Constructor initializes the prices list
    public StockSpanner() {
        prices = new ArrayList<>();
    }

    /**
     * This method calculates the span of the stock's price for the current day.
     * @param price: the stock's price for the current day
     * @return span of the stock's price for the current day
     */
    public int next(int price) {
        // Add the current price to the prices list
        prices.add(price);

        // Start the span count with 1 (for the current day itself)
        int span = 1;

        // Traverse the list backwards starting from the day before the current day
        for (int i = prices.size() - 2; i >= 0; i--) {
            // If the price of the previous day is less than or equal to the current price
            if (prices.get(i) <= price) {
                // Increase the span count
                span++;
            } else {
                // If we find a price that's greater than the current price, break out of the loop
                break;
            }
        }
        // Return the span count for the current price
        return span;
    }
}

Time Complexity: O(N) for each call to next, where N is the number of prices already processed.

Space Complexity: O(N), for storing N prices.

Can we do better than above solution? Can some data structure other than List help in optimizing the solution? How can we eliminate unnecessary lookup (minimize the traversal of the List)?

Optimized Solution

Key Idea:

Instead of keeping track of every individual price, we’re interested in keeping track of consecutive days where the price was less than or equal to the price of the current day.

The moment we hit a day where the price is higher, we don’t need to remember the individual prices of the days before it.

For this, we can use a Stack data structure to store pairs of price and its span.

In simpler words, if today’s price is larger than the last few days, then today’s span will “cover” all those days. And that’s exactly what the stack will help us track!

Let’s implement the solution in Java:

class StockSpanner {
    // Stack to store pairs of {price, span}
    Stack<int[]> stack;

    // Constructor initializes the stack
    public StockSpanner() {
        stack = new Stack<>();
    }

    /**
     * This method calculates the span of the stock's price for the current day.
     * @param price: the stock's price for the current day
     * @return span of the stock's price for the current day
     */
    public int next(int price) {
        // Start the span count with 1 (for the current day itself)
        int span = 1;

        // Check if the stack is not empty and if the price at the top of the stack 
        // is less than or equal to the current price
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            // If so, then add the span of the top price to the current span
            // This means the previous prices (days) are included in the current day's span
            span += stack.pop()[1];
        }

        // Push the current price and its span to the stack
        stack.push(new int[]{price, span});

        // Return the calculated span
        return span;
    }
}

Time Complexity: The worst-case for a single call to next is O(N) (when all elements are popped), but since each price is pushed and popped exactly once, the amortized time complexity over N calls to next is O(N).

Space Complexity: O(N), for storing N prices.

Key Concepts

1. Amortized Analysis: Although the worst-case time for a single operation might be high, the average time over a sequence of operations might be much lower.
2. Stack Data Structure: Helps in maintaining state efficiently, especially when dealing with sequenced data where recent items have a higher significance.

Let’s dig deeper into the intuition behind using Stack to solidify our understanding:

Intuition:

Consecutive Days

When you consider any day’s price, if the price is less than or equal to the next day’s price, then its span will always be included in the span of the next day whenever the next day’s price is used for comparison.

Use of Stack:

• Storing Prices with Span: In the stack, instead of just storing the price, we store the price paired with its span. This helps us understand how many days we need to “jump back” if the current price is greater.
• Pushing to Stack: When we add a new price, we compare it with the price at the top of the stack (most recent). If the current price is greater, we pop the top of the stack. We continue this until we find a price that’s higher or the stack becomes empty. Each time we pop, we’re essentially saying, “The current day’s price is greater than all these popped days, and they can be included in the span.”
• Stack’s Nature: The beauty of a stack is its LIFO (Last-In, First-Out) nature. The most recent prices are the ones we check first, and these are precisely the ones we want to compare our new price with.

Skipping Over Days

Consider you’re at day 100 with a certain price. The prices of days 90 to 99 are all less than the price at day 100. If day 101 comes with a higher price than day 100, then inherently, days 90–99 are also lower than day 101 (because they were lower than day 100). This means that the span of day 101 can directly “jump over” days 90–99 without having to individually check them. This “jumping over” is effectively facilitated by the stack.

Efficiency

Since each price is pushed onto the stack once and popped off the stack once, we achieve an amortized time complexity of O(1) per operation, which is significantly more efficient than the brute force method.

In essence, the stack helps to “remember” the relevant prices in their order and allows us to efficiently skip over days that aren’t pertinent to the span calculation for the current day.

Please follow me on Medium if you found this post useful. More to come!