How do you solve Online Stock Span on LeetCode?

Online Stock Span (LeetCode #901) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a stack allows for efficient tracking of spans without needing to iterate through all previous prices.

What is the brute force solution for Online Stock Span?

The brute force approach for Online Stock Span is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each day's price against all previous days to calculate the span. This is straightforward but inefficient as it requires checking multiple days for each new price. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Online Stock Span?

Online Stock Span uses the following concepts: Stack, Design, Monotonic Stack, Data Stream. The recommended patterns to study are: Monotonic Stack, Array.

What are the interview tips for Online Stock Span?

Explain your thought process clearly while coding — this helps interviewers understand your approach. Consider edge cases and discuss them with the interviewer. Practice writing clean and efficient code, as readability is important.

What are common mistakes when solving Online Stock Span?

Failing to manage the stack correctly, leading to incorrect spans. Not considering edge cases, such as when the stack is empty.

#901

Online Stock Span

Medium

StackDesignMonotonic StackData StreamMonotonic StackArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a stack allows us to efficiently track the spans of stock prices. By storing indices of prices, we can quickly determine how many consecutive days have prices less than or equal to the current price.

⚙️

Algorithm

4 steps

1Step 1: Initialize an empty stack and a variable to store the current index.
2Step 2: For each new price, pop elements from the stack until the top of the stack has a price greater than the current price.
3Step 3: If the stack is empty, the span is the current index + 1; otherwise, the span is the difference between the current index and the index at the top of the stack.
4Step 4: Push the current index onto the stack.

solution.py12 lines

1class StockSpanner:
2    def __init__(self):
3        self.stack = []
4        self.index = 0
5
6    def next(self, price: int) -> int:
7        while self.stack and self.stack[-1][0] <= price:
8            self.stack.pop()
9        span = self.index + 1 if not self.stack else self.index - self.stack[-1][1]
10        self.stack.append((price, self.index))
11        self.index += 1
12        return span

ℹ

Complexity note: The time complexity is O(n) because each price is pushed and popped from the stack at most once. The space complexity is O(n) due to the storage of prices in the stack.

1Using a stack allows for efficient tracking of spans without needing to iterate through all previous prices.
2Understanding the relationship between the current price and previous prices is key to optimizing the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.