How to Solve Online Stock Span

The Online Stock Span problem requires calculating the span of stock prices using an efficient stack-based approach. A stack is used to track previous prices and determine how many consecutive days the stock price was lower than or equal to the current day's price. The solution optimizes the process with an average time complexity of O(1) per query by leveraging a monotonic stack.

Problem Statement

You are tasked with designing an algorithm that tracks daily stock price quotes and calculates the span for each price. The span of a stock's price for a given day is defined as the number of consecutive days (starting from the current day and moving backwards) on which the stock price was less than or equal to the current day's price.

You need to implement the StockSpanner class with a method next(int price), which accepts an integer price and returns the span of the stock's price for the current day. The function will be called several times with different price values.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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, because the last 4 prices (including today's price of 75) were less than or equal to today's price. stockSpanner.next(85); // return 6

Constraints

• 1 <= price <= 105
• At most 104 calls will be made to next.

Solution Approach

Stack-based Span Calculation

The key to solving this problem efficiently is using a stack to maintain the indices of prices in a monotonic decreasing order. For each price, we compare it with the top of the stack and pop from the stack while the current price is greater than or equal to the prices at those indices. The span for the current price is determined by the difference between the current index and the index of the last price that was greater than or equal to it.

Maintaining Monotonicity

By ensuring the stack remains in a monotonic decreasing order, we can efficiently find the number of consecutive days for which the price was less than or equal to the current price. Each element in the stack represents a price that was the largest among all previous prices for that day, helping us skip redundant comparisons and minimize time complexity.

Optimizing with O(1) Complexity

Each call to next() involves a constant number of operations. By maintaining a stack of prices, we reduce the need to traverse all previous days' prices, allowing us to calculate the span for each new price in O(1) average time complexity. This optimization ensures the solution scales efficiently with larger inputs.

Complexity Analysis

The time complexity of the solution is O(1) per operation on average due to the stack's monotonic property, though in the worst case (if each price is strictly increasing), the time complexity can be O(n) for a series of calls. The space complexity is O(n), where n is the number of calls made to the next() function, as each price might be stored in the stack at once.

What Interviewers Usually Probe

• Candidate understands the importance of using a stack for efficient state management.
• Candidate demonstrates the ability to optimize a brute-force solution to O(1) complexity.
• Candidate is able to articulate the trade-offs between time complexity and space complexity in stack-based problems.

Common Pitfalls or Variants

Common pitfalls

• Not maintaining the stack in monotonic order, which can lead to incorrect span calculations.
• Failing to efficiently handle the worst-case scenario where all stock prices are in increasing order.
• Not fully utilizing the stack’s properties, such as avoiding redundant calculations for previously processed prices.

Follow-up variants

• Implementing a solution with an alternative data structure (e.g., queue or array) for span calculation.
• Handling the problem with multiple stock spans, each with separate stock price inputs.
• Optimizing for a stream of data with real-time updates and dynamic span calculations.

How GhostInterview Helps

• GhostInterview provides you with targeted exercises that help you master stack-based state management for problems like this.
• By solving this problem with GhostInterview, you’ll gain confidence in using monotonic stacks for efficient solutions.
• GhostInterview's detailed problem breakdown ensures you focus on optimizing both time and space complexity, a critical skill for coding interviews.

Topic Pages

• Stack
• Design
• Monotonic Stack
• Data Stream

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

How do I calculate the stock span using a stack?

By maintaining a stack in monotonic decreasing order, you can calculate the span of a stock price by comparing it to the prices at the indices in the stack. The span for the current price is the difference between the current index and the index of the last price that was greater than or equal to it.

What is the time complexity of the solution?

The average time complexity is O(1) per operation due to the stack's efficient management. In the worst case, the time complexity can be O(n) if all prices are strictly increasing.

What does monotonic stack mean in the context of this problem?

A monotonic stack ensures that the prices in the stack are in a decreasing order. This property allows efficient span calculation by removing redundant comparisons for previously processed prices.

What other data structures could be used for the Online Stock Span problem?

While a stack is the most efficient data structure for this problem, alternatives such as arrays or queues could be used, but they would not offer the same performance, especially for larger inputs.

How does GhostInterview help with this problem?

GhostInterview provides guided solutions and practice problems that focus on stack-based state management, helping you master the techniques necessary for efficient problem-solving in coding interviews.