algoadvance

Leetcode 901. Online Stock Span

Problem Statement

Design a data structure that will be used to record a sequence of stock prices, and it should support the following operations:

  1. next(int price):
    • Records a new price.
    • Returns the span of the stock’s price for the current day.

The span of the stock’s price on a given day is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today’s price.

For example, if the stock price is recorded as [100, 80, 60, 70, 60, 75, 85], then the spans are [1, 1, 1, 2, 1, 4, 6].

Clarifying Questions

  1. Q: Is there any expected upper limit on the number of days for which stock prices can be recorded?
    • A: No explicit upper limit is provided; the data structure should handle any reasonably large input.
  2. Q: Should the solution optimize for frequent calls to next?
    • A: Yes, the solution should aim for efficient processing of each next call as it will be invoked frequently.

Strategy

To efficiently compute the span, we can utilize a stack to keep track of the stock prices and their corresponding spans. Here’s the strategy in detail:

  1. Stack Usage:
    • We’ll use a stack to store pairs of (price, span).
    • For each new price, we’ll calculate its span by comparing it with the prices in the stack, starting from the top.
    • If a price in the stack is less than or equal to the current price, we pop it and add its span to the current span.
    • This ensures that each price only gets processed once, leading to an efficient solution.
  2. Span Calculation:
    • Initialize current span as 1 (since at least the current day is included).
    • Continue popping from the stack while the price at the stack’s top is less than or equal to the current price.
    • Add the spans of all popped prices to the current span.
    • Push the current price and its calculated span onto the stack.

Code

import java.util.Stack;

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

    public StockSpanner() {
        stack = new Stack<>();
    }

    public int next(int price) {
        int span = 1;
        
        // Calculate the span for the current price
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        
        // Push the current price and its span onto the stack
        stack.push(new int[] {price, span});
        
        return span;
    }
}

Time Complexity

Thus, the amortized time complexity of each next call is O(1).

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