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 — 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 instant their answer becomes knowable.

💡 Fun fact: Sum of Subarray Minimums has n(n+1)/2 subarrays — 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.

The one-line idea: 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, an area, 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:

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:

subarrays where nums[i] is the minimum  =  left x right
contribution to the total               =  nums[i] x left x 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 — a range is max − min, so 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.

element  value  left span  right span  subarrays  contribution
   0       3        1           1          1          3        [3]
   1       1        2           3          6          6        [3,1],[1],[1,2],[3,1,2],[1,2,4],[3,1,2,4]
   2       2        1           2          2          4        [2],[2,4]
   3       4        1           1          1          4        [4]
                                          ---        ----
                                          10 = 4x5/2   17

Ten subarrays, each counted exactly once, and the total is 17. Verify by hand: mins are 3, 1, 1, 1, 1, 1, 2, 2, 4, 1 — summing to 17. No subarray was ever built.

4. Where you'll actually meet this

• Financial analytics. Online Stock Span is a named indicator: how many consecutive prior days did this price dominate? Trading systems compute it incrementally, exactly this way.
• Retail pricing. Final Prices With a Special Discount is the "next smaller price" rule from actual promotion engines.
• Time-series and monitoring. "How long has this metric been the highest?" over a stream, in O(1) amortised per point.
• Layout and rendering. Nearest-taller-neighbour queries drive skyline computation and column layout.
• Compilers and profilers. Span computations over call stacks and flame graphs reduce to the same boundary questions.

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(n) 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) amortised per query.

▶ 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; the problem specifies a modulus for a reason, and applying it only at the end can still overflow along the way.
• 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

1. The pop is the answer. An element's boundary becomes knowable exactly when something beats it.
2. One sweep gives both sides — the left boundary is whatever is still on the stack when you push.
3. Invert the question. "Which subarrays is this element the minimum of?" replaces enumeration with multiplication.
4. Break ties asymmetrically, strict on one side and non-strict on the other, or duplicates ruin the count.
5. Indices and sentinels, every time.
6. Amortised O(n), because each index enters and leaves once — and you should be able to prove it in a sentence.
7. 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.