</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Monotonic stack flowchart: each pop settles a boundary (chalkboard)

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.


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:

Contribution counting formulas: subarrays and contribution via left x right (chalkboard)

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.

Sum of Subarray Minimums worked table for [3,1,2,4] (chalkboard)

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^13 at 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

  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. Amortized 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.

Final Prices With a Special Discount in a Shop

Core idea: the discount on item i is the price of the nearest item to its right that is cheaper-or-equal. That phrase, next smaller-or-equal element to the right, is a textbook monotonic-stack pattern. Keep a stack of "items still waiting for their discount" with prices strictly increasing from bottom to top; when a cheaper-or-equal item shows up, it settles every waiting item it can, in one O(n) left-to-right sweep.

Problem, rephrased

A shop is running an odd promotion down one shelf, and the register needs the checkout price for every item. This is LeetCode 1475: Final Prices With a Special Discount in a Shop. You're given an integer array prices, where prices[i] is the marked price of the i-th item on the shelf, read left to right.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.