Similar Problems

Similar Problems not available

Online Stock Span - Leetcode Solution

Companies:

LeetCode:  Online Stock Span Leetcode Solution

Difficulty: Medium

Topics: design stack  

Problem Statement:

Write a class StockSpanner which 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 today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

Example:

StockSpanner spanner = new StockSpanner();

spanner.next(100); // returns 1

spanner.next(80); // returns 1

spanner.next(60); // returns 1

spanner.next(70); // returns 2

spanner.next(60); // returns 1

spanner.next(75); // returns 4

spanner.next(85); // returns 6

Solution:

Approach: We can solve this problem using stack data structure. We will keep storing the stock prices in the stack and for every new stock, we will compare it with the topmost stock price in the stack. If the new stock price is greater than the topmost stock in the stack, then we will just pop the topmost stock until either the stack becomes empty or the topmost stock price is greater than current stock price. We will keep a count of the number of stocks popped from the stack and add it to the result.

Algorithm:

  1. Keep two stacks of stock prices and stock span respectively.

  2. For each new stock, calculate its span by comparing it with the last stock stored in the stack.

  3. If the new stock price is greater than the last stock price, keep popping the stocks from the stack until either the stack becomes empty or the topmost stock price is greater than the current stock price.

  4. Keep a count of the number of stocks popped and add it to the span of the current stock.

  5. Push the current stock price and its span into the stacks.

  6. Return the span of the current stock.

Code:

Below is the code implementation of the above-mentioned algorithm.

class StockSpanner {

Stack<Integer> prices;
Stack<Integer> spans;

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

public int next(int price) {
    int span = 1;

    while(!prices.isEmpty() && prices.peek() <= price) {
        prices.pop();
        span += spans.pop();
    }

    prices.push(price);
    spans.push(span);

    return span;
}

}

Time Complexity: The time complexity of the above algorithm is O(N) where N is the number of stock prices given as input. As we are iterating over the stack until it becomes empty or the topmost stock price is greater than the current stock price, in the worst case, we may have to iterate over the entire stack.

Space Complexity: The space complexity of the above algorithm is O(N) as we are using two stacks to store the stock prices and their respective span.

Online Stock Span Solution Code

1