Monotonic Stack
What is this?
Ask a queue of people, each holding a number, this question: how many people behind you were smaller than you, in an unbroken run? Nobody can answer while smaller people keep arriving, because their run is still growing. The moment someone larger shows up, every smaller person's run is over and their answer is final.
That is a monotonic stack. Elements wait on it until something beats them, and the pop is the moment their answer becomes known.
Fun fact: Sum of Subarray Minimums has
n(n+1)/2subarrays (a million elements gives half a trillion of them) and is solved in a single linear pass by inverting the question. Instead of asking "what is the minimum of each subarray?", ask "for each element, how many subarrays is it the minimum of?" That count is(distance to the nearest smaller on the left) × (distance to the nearest smaller on the right), and multiplying it by the value gives the element's total contribution. Enumeration becomes arithmetic.
🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In short: a monotonic stack answers "what is the nearest smaller (or greater) element on each side?" for every position in O(n). Every problem here is that question plus one step of arithmetic: a span, a discount, or a count of the subarrays an element dominates.
1. The four variants
The stack's order and the comparison decide which question you are answering:
| You want | Stack order | Pop while |
|---|---|---|
| nearest greater to the right | decreasing | stack top < incoming |
| nearest smaller to the right | increasing | stack top > incoming |
| nearest greater to the left | decreasing | (read the stack top before pushing) |
| nearest smaller to the left | increasing | (read the stack top before pushing) |
Left-side answers come free: whatever remains on the stack when you push is, by construction, the nearest element on the left that has not been beaten. That is why a single sweep can produce both boundaries.
2. Contribution counting
The step that turns this from a lookup tool into a counting tool. For element i with left = distance to the nearest strictly-smaller element on the left and right = distance to the nearest smaller-or-equal on the right:
The asymmetry matters: one side must use strict < and the other <=. If both sides used the same comparison, subarrays containing duplicate minima would be counted twice (or zero times). This is the single most common bug in the chapter, and it only shows up on inputs with repeats.
Sum of Subarray Ranges then comes almost free since a range is max − min: run the whole thing twice, once counting minimum-contributions and once maximum-contributions, and subtract.
3. A 30-second worked example
arr = [3, 1, 2, 4], summing the minimum of every subarray.
Ten subarrays, each counted exactly once, and the total is 17. Verify by hand: the minimums, in order of start index, are 3, 1, 1, 1, 1, 1, 2, 2, 4 and 1, which sum to 17. No subarray was ever built.
4. Where you'll actually meet this
- Price feeds. Online Stock Span asks how many consecutive prior days a price was at or below today's. The stack answers it per tick without rescanning history.
- Metric streams. "How long has this metric been the highest?" over a stream is the same question, in O(1) amortized per point.
- Next-smaller rules. Final Prices With a Special Discount is the plain "next smaller-or-equal element" sweep. Any rule of the form "the first later item that beats this one" reduces to it.
5. Problems in this chapter
Next Greater Element I
For each element of one array, find the next greater element in another. The introduction: build a next-greater map with one decreasing-stack sweep, then answer queries in O(1).
Pattern: decreasing stack + lookup map. Target: O(n + m) time, O(m) space.
Online Stock Span
Streaming: report how many consecutive prior days had a price no higher than today's. Pop dominated days and absorb their spans, so each day is popped once overall.
Pattern: decreasing stack with span accumulation. Target: O(1) amortized per query, O(n) space.
Final Prices With a Special Discount in a Shop
Subtract the next smaller-or-equal price from each price. The plainest "next smaller element" sweep in the chapter.
Pattern: increasing stack of indices. Target: O(n) time, O(n) space.
Sum of Subarray Minimums
Sum the minimum of every subarray. Contribution counting with the strict/non-strict asymmetry that makes duplicates behave.
Pattern: boundaries → counts → arithmetic. Target: O(n) time, O(n) space.
Sum of Subarray Ranges
Sum max − min over every subarray. Two contribution passes, subtracted.
Pattern: contribution counting, twice. Target: O(n) time, O(n) space.
6. Common pitfalls
- Symmetric comparisons on both sides. With duplicates,
<on the left and<=on the right is mandatory, otherwise subarrays are double-counted or dropped. - Storing values, not indices. Spans and widths need positions.
- No sentinel. Elements left on the stack at the end never get their right boundary; append a sentinel or run one extra iteration.
- Absorbing spans wrongly in the stock-span problem. When you pop a dominated day, add its accumulated span to yours; dropping it makes the answer too small.
- Overflow. Sums of subarray minima grow fast (about
1.35 * 10^13at the lesson's limits). That fits a 64-bit integer but not a 32-bit one, so take the modulus on the running total. - Assuming O(n²) because of the nested
while. Each index is pushed and popped once. Say that before the interviewer asks. - Confusing "next greater" with "next greater to the right, circularly." Circular variants need two passes over the array.
7. Key takeaways
- The pop is the answer. An element's boundary becomes knowable exactly when something beats it.
- One sweep gives both sides: the left boundary is whatever is still on the stack when you push.
- Invert the question. "Which subarrays is this element the minimum of?" replaces enumeration with multiplication.
- Break ties asymmetrically, strict on one side and non-strict on the other, or duplicates ruin the count.
- Indices and sentinels, every time.
- Amortized O(n), because each index enters and leaves once, and you should be able to prove it in a sentence.
- Why interviewers love it: the technique looks like a trick until you can explain the boundary argument, at which point half a dozen "hard" problems become the same problem.
Order: Next Greater Element I → Online Stock Span → Final Prices With a Special Discount → Sum of Subarray Minimums → Sum of Subarray Ranges.
Online Stock Span
Core idea: Keep a stack of
(price, span)pairs in strictly decreasing price order. Each new price absorbs every prior entry whose price is at most its own: pop those entries and add up their spans. The collapsed run becomes a single stack entry carrying the combined span, so each day is pushed and popped at most once.
Problem, rephrased
You're building a live ticker for a single stock. Once per trading day one closing price streams in, and the chart must annotate it immediately. You implement a class: StockSpanner() initializes the tracker, and each call next(price) feeds in today's closing price.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson