Online Stock Span
Problem
StockSpanner that receives one daily stock price at a
time through next(price). Each call must return today's span: the length
of the longest run of consecutive days ending today (today included) on which the price was
less than or equal to today's price.next: 100, 80, 60, 70, 60, 75, 85Output1, 1, 1, 2, 1, 4, 6next: 5, 5, 5Output1, 2, 31 ≤ price ≤ 105 · at most 104 calls to next
Try it yourself
class StockSpanner {
public StockSpanner() {
}
public int next(int price) {
}
}
(price, span) and fold each popped span into today's.Instinct Each element needs its nearest bigger or smaller neighbour (next warmer day, span, widest bar) - keep a sorted stack of waiting indices.
Memory hack Tall people block the view - a newcomer kicks out everyone shorter waiting behind, and each kicked-out person just found their answer.
Open the Monotonic Stack guide →Approaches
Brute ForceStore History, Walk Back Day by Day
O(n) per callSpace O(n)Remember every price. On each call, step backwards one day at a time while the price is at most today's, counting days. This follows the definition directly.
class StockSpanner { private final List<Integer> prices = new ArrayList<>(); public StockSpanner() { } public int next(int price) { prices.add(price); int span = 0; for (int j = prices.size() - 1; j >= 0 && prices.get(j) <= price; j--) { span++; } return span; } }
Simple, but a long rising streak makes every call scan the whole history.
BetterJump Back Using Earlier Spans
O(1) amortizedSpace O(n)Also remember each day's span. If yesterday's price is ≤ today's, every day
inside yesterday's span is too, so jump over all of them at once:
j -= span[j]. The jumps visit only the “previous greater”
chain, giving amortized constant time.
class StockSpanner { private final List<Integer> prices = new ArrayList<>(); private final List<Integer> spans = new ArrayList<>(); public StockSpanner() { } public int next(int price) { int span = 1; int j = prices.size() - 1; // previous day while (j >= 0 && prices.get(j) <= price) { span += spans.get(j); j -= spans.get(j); // skip the whole block day j already covered } prices.add(price); spans.add(span); return span; } }
Fast, but keeps every past day in memory even though most are useless.
OptimalMonotonic Stack of (price, span)
O(1) amortizedSpace O(n) worstKeep a stack whose prices strictly decrease from bottom to top. Today's price pops every entry ≤ it and absorbs their spans; those days are hidden behind today forever, so discarding them is safe. Each day is pushed and popped once.
class StockSpanner { private final Deque<int[]> stack = new ArrayDeque<>(); // {price, span} public StockSpanner() { } public int next(int price) { int span = 1; while (!stack.isEmpty() && stack.peek()[0] <= price) { span += stack.pop()[1]; // absorb the dominated block } stack.push(new int[]{price, span}); return span; } }
Same speed as the jump trick but stores only days that can still matter.
≤, not < — equal prices belong
to the span.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Store History, Walk Back Day by Day | O(n) per call | O(n) |
| Better | Jump Back Using Earlier Spans | O(1) amortized | O(n) |
| Optimal | Monotonic Stack of (price, span) | O(1) amortized | O(n) worst |
- Popping only on strictly smaller prices — equal prices must extend the span.
- Pushing just the price and losing the span of the popped block.
- Forgetting to count today itself (span starts at 1).
- Clarify the online setting: you cannot look ahead, only at history.
- Explain amortized O(1): total pops never exceed total pushes.
- Note the stack holds the “previous greater” chain of today's price.