Online Stock Span
Online Stock Span is a medium monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (monotonic stack of price and span), runs in O(1) amortized per call time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (walk back over all prices) up.
Problem
Design a class StockSpanner that receives a stock’s price once per day and reports that day’s span.
The span of today’s price is the number of consecutive days, ending with today and going backwards, on which the price was less than or equal to today’s price.
StockSpanner()creates the object.int next(int price)records today’s price and returns its span.
Examples
Example 1
- Input
StockSpanner(), next(30), next(25), next(27), next(27), next(40), next(10)- Output
1, 1, 2, 3, 5, 1- Why
- On the day of 27 (second time), the run back from today is 27, 27, 25, so the span is 3. The 40 is at least every earlier price, so its span covers all 5 days.
Example 2
- Input
StockSpanner(), next(7), next(7), next(7)- Output
1, 2, 3- Why
- Equal prices count, because the condition is "less than or equal".
Constraints
1 <= price <= 10^5- At most
10^4calls tonext.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (walk back over all prices) | O(n) per call | O(n) |
| Optimal (monotonic stack of price and span) | O(1) amortized per call | O(n) |
1Brute force (walk back over all prices)
O(n) per callWith rising prices, each call walks over the whole history.O(n)Every price is stored.Store every price. For each new price, walk backwards from yesterday while the stored prices are <= today's price, counting the days.
- Append price to the list.
- Start at the previous index and move left while list[i] <= price.
- Return the number of days covered, including today.
class StockSpanner {
private final List<Integer> prices = new ArrayList<>();
public StockSpanner() {
}
public int next(int price) {
prices.add(price);
int span = 1;
int i = prices.size() - 2;
while (i >= 0 && prices.get(i) <= price) {
span++;
i--;
}
return span;
}
}class StockSpanner:
def __init__(self):
self.prices = []
def next(self, price: int) -> int:
self.prices.append(price)
span = 1
i = len(self.prices) - 2
while i >= 0 and self.prices[i] <= price:
span += 1
i -= 1
return spanclass StockSpanner {
vector<int> prices;
public:
StockSpanner() {}
int next(int price) {
prices.push_back(price);
int span = 1;
int i = (int)prices.size() - 2;
while (i >= 0 && prices[i] <= price) {
span++;
i--;
}
return span;
}
};class StockSpanner {
constructor() {
this.prices = [];
}
next(price) {
this.prices.push(price);
let span = 1;
let i = this.prices.length - 2;
while (i >= 0 && this.prices[i] <= price) {
span++;
i--;
}
return span;
}
}2Optimal (monotonic stack of price and span)
O(1) amortized per callEach price is pushed once and popped at most once over all calls.O(n)In the worst case (falling prices) every pair stays on the stack.Keep a stack of (price, span) pairs whose prices strictly decrease from bottom to top. A new price pops every pair with a price <= it and adds their spans to its own, because those days are all covered. Then it is pushed with the merged span.
- span = 1.
- While the stack is non-empty and its top price <= price: span += top span, pop.
- Push (price, span) and return span.
class StockSpanner {
private final Deque<int[]> stack = new ArrayDeque<>();
public StockSpanner() {
}
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;
}
}class StockSpanner:
def __init__(self):
self.stack = [] # (price, span), prices strictly decreasing
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return spanclass StockSpanner {
vector<pair<int, int>> st; // (price, span), prices strictly decreasing
public:
StockSpanner() {}
int next(int price) {
int span = 1;
while (!st.empty() && st.back().first <= price) {
span += st.back().second;
st.pop_back();
}
st.push_back({price, span});
return span;
}
};class StockSpanner {
constructor() {
this.stack = []; // [price, span], prices strictly decreasing
}
next(price) {
let span = 1;
while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
span += this.stack.pop()[1];
}
this.stack.push([price, span]);
return span;
}
}Edge cases to test
- The very first price (span 1)
- Strictly increasing prices (span grows by one each day)
- Strictly decreasing prices (span is always 1)
- Equal prices, which extend the span
Hints
Hint 1
The span is how far back you can walk from today while prices are <= today's price.
Hint 2
Once a higher price arrives, the smaller prices before it can never stop a later walk on their own: the higher price stops it first, or is absorbed too.
Hint 3
Keep a stack of (price, span) pairs with decreasing prices, and merge popped spans into today's.
FAQ
What is the best time complexity for Online Stock Span?
Optimal (monotonic stack of price and span) runs in O(1) amortized per call time and O(n) extra space. Each price is pushed once and popped at most once over all calls.
Which pattern does Online Stock Span use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Online Stock Span?
Yes. Brute force (walk back over all prices) takes O(n) per call time and O(n) space. Store every price.
Which edge cases should I test for Online Stock Span?
The very first price (span 1); Strictly increasing prices (span grows by one each day); Strictly decreasing prices (span is always 1); Equal prices, which extend the span.