algoadvance

Leetcode 901. Online Stock Span

Problem Statement

The problem is to design a system for calculating the stock span of each day based on daily stock prices. The stock span is defined as the number of consecutive days leading up to the current day where the stock price was less than or equal to the current day’s price, including the current day itself.

Implement the StockSpanner class:

Example:

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
stockSpanner.next(85);  // return 6

Clarifying Questions

  1. Are there any constraints on the input values for the stock prices?
    • Yes, 1 <= price <= 10^5 and there may be up to 10^5 calls to the next method.
  2. How should we handle the input/output format for testing?
    • The next method should return the stock span for given day’s price.

Strategy

To solve this problem efficiently, we can use a stack to keep track of the stock prices and their corresponding spans. Here is the strategy:

  1. Use a Stack: Each element in the stack will be a pair, where the first element is the stock price and the second element is the span of that price.
  2. Maintain Span: For each new price, pop elements from the stack as long as the price at the top of the stack is less than or equal to the current price.
  3. Calculate Span: The span for the current price is 1 plus the sum of spans of all the popped elements.
  4. Push Current Price: Push the current price and its calculated span onto the stack.

This way, the stack helps us efficiently compute the spans of stock prices in O(1) average time per call.

Code

#include <stack>
#include <utility>

class StockSpanner {
private:
    std::stack<std::pair<int, int>> stockStack; // Pair (price, span)

public:
    StockSpanner() {
        // Initialize necessary data structures
    }
    
    int next(int price) {
        int span = 1;
        // Calculate span based on previous prices
        while (!stockStack.empty() && stockStack.top().first <= price) {
            span += stockStack.top().second;
            stockStack.pop();
        }
        // Push the current price and its span onto the stack
        stockStack.push({price, span});
        return span;
    }
};

Time Complexity

The time complexity for each next call is amortized O(1). This is because each price is pushed and popped from the stack exactly once, leading to a total time complexity of O(n) for n calls to the next method. Thus, the average time complexity per operation is constant.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI