Stock span problem

Online Stock Span

Problem Overview

The Online Stock Span is a problem that revolves around stock price calculations over days with the help of data structures. The goal is to calculate the "span" of stock prices, where the span is defined as the number of consecutive days up to the current day, the stock price was less than or equal to today’s price.

This problem is quintessential for understanding how Stack data structures can be utilized to efficiently solve problems associated with consecutive or previous elements in a sequence.

Understanding the Problem

Let's break down the problem for better comprehension:

1. Input: Each time a price is given, we are to determine and return the span of that day's price.
2. Output: Return the span for each price.
3. Definition of Span: For a given day's stock price, its span is the count of consecutive previous days where the stock's price was less than or equal to the current day's price, including the current day itself.

For example, consider the stock prices over five days are [100, 80, 60, 70, 60, 75, 85]. The spans for these would be [1, 1, 1, 2, 1, 4, 6].

Key DSA Concepts and Theory

Stack Data Structure

• Definition: A stack is a linear data structure which follows the Last In First Out (LIFO) principle.
• Operations: The primary operations of a stack are push (to insert an element), pop (to remove the top element), and peek or top (to view the top element).
• Use Case in this Problem: Stacks are employed to keep track of indexes of prices in a fashion where their corresponding prices are always in decreasing order from the bottom to the top of the stack.

Solution Approach

To efficiently solve this problem using the stack, we need to maintain a stack that supports retrieving the nearest greater element for each stock price.

Approach Steps:

1. Initialization: Initialize a stack S that will store pairs of values (price, span).
2. Iterate through each day's price:
   • If the stack is not empty and the current price is greater than the price at the index stored in the stack's top, keep popping from the stack.
   • Calculate the span for the current price as the difference between the current day's index and the index of the last element in the stack (after all the pops).
   • Push the current day's index and its calculated span onto the stack.
3. Return Span for each of the prices processed.

C++ Implementation

class StockSpanner {
public:
    std::stack<std::pair<int, int>> S; // stack to store {price, span}
    
    StockSpanner() {}
    
    int next(int price) {
        int span = 1;
        while (!S.empty() && S.top().first <= price) {
            span += S.top().second;
            S.pop();
        }
        S.push({price, span}); // push current price and its span
        return span;
    }
};

Java Implementation

class StockSpanner {
    private Stack<int[]> stack; // stack to store (price, span)
    
    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

Time and Space Complexity Analysis

• Time Complexity: Each element is pushed and popped from the stack at most once. Hence, the time complexity for next() is amortized O(1).
• Space Complexity: In the worst case, every call to next() pushes an element onto the stack, leading to O(N) space complexity, where N is the number of calls to next().

Common Mistakes to Avoid

• Misunderstanding Span Calculation: Ensure to correctly accumulate the span by adding spans of popped elements.
• Incorrect Order in Stack: The stack should maintain prices in a non-increasing order from top to bottom for the span calculation to work correctly.

Similar Problems on LeetCode

• Problem 739: Daily Temperatures
• Problem 901: Minimum Remove to Make Valid Parentheses

Additional Resources and References

• GeeksforGeeks - Stock Span Problem
• Stack Data Structure on GeeksforGeeks

This problem helps strengthen understanding of stack manipulation and is pivotal for problems that involve previous or consecutive element comparisons in scenarios like stock pricing, temperature generation, etc.