DSA Roadmap/Stack

Monotonic Stack

Turn 'find the next/previous greater or smaller element' from an O(n²) nested scan into a single O(n) pass by keeping the stack sorted at all times.

!!!3/5Theory: 2h9 problems

What problem this actually solves

A huge family of array problems boils down to: "for every element, find the nearest element to its left/right that is bigger (or smaller) than it." The brute-force answer is a nested loop — for each index, walk outward until you find a match — which is O(n²) and gets rejected instantly against any n <= 10^5 constraint. The Monotonic Stack pattern answers the exact same question in a single O(n) pass by keeping a stack that is always sorted (strictly increasing or strictly decreasing from bottom to top), discarding elements the moment they become permanently irrelevant.

This is one of the highest-leverage patterns on the whole roadmap: once you recognize it, an intimidating-looking problem collapses into ~10 lines of code you can write from memory.

Recognizing it in a problem statement

Look for phrasing built around relative order among positions, not arbitrary range queries:

  • "Next greater element", "next smaller element", "previous greater/smaller"
  • "How many days until a warmer temperature" (a distance-to-next-greater question)
  • "Span" of a value (how far back does a run of "not bigger than me" extend)
  • "Largest rectangle" / "histogram" (each bar needs its left/right boundary — the nearest shorter bar on each side)
  • "Trapping water" between bars
  • Greedy digit/character removal to build the smallest/largest possible result ("remove k digits", "remove duplicate letters")
  • "How many cars merge into one fleet" — anything where a later element can only be "blocked" by, or "absorb", an unresolved earlier one

If you catch yourself wanting to write for i: for j in range(i+1, n): ... to compare every pair, stop and ask whether the comparisons only ever care about the nearest qualifying neighbor. If so, a monotonic stack almost certainly applies.

The template

The stack holds indices, not values (more on why below). At each step, before pushing the current index, pop off everything that the current element invalidates:

def monotonic_stack_template(nums): n = len(nums) result = [-1] * n # or 0, or whatever "no answer" means stack = [] # holds indices, kept monotonic for i in range(n): while stack and CONDITION(nums[stack[-1]], nums[i]): j = stack.pop() # nums[i] is the answer for index j — resolve it now result[j] = i # or nums[i], or i - j, depending on the problem stack.append(i) # anything left on the stack has no answer to its right return result

Everything about the pattern is captured by choosing CONDITION and what you do at resolution time.

Increasing vs. decreasing: pick the right invariant

Stack invariantPop condition (before push)What a pop resolvesClassic use case
Monotonic decreasing (top = smallest so far)stack top < currentNext greater element for the popped indexDaily Temperatures, Next Greater Element
Monotonic increasing (top = largest so far)stack top > currentNext smaller element for the popped indexLargest Rectangle in Histogram (right boundary)

The mirror-image versions — scanning right to left, or popping with <=/>= instead of </> — give you previous greater/smaller instead of next, and control how ties are broken (whether equal elements count as "greater"). Get in the habit of explicitly stating, out loud, which of the four variants (next/previous × greater/smaller) you need before writing code — this is exactly the kind of precision a Senior-level interviewer is listening for.

Why this is O(n) despite the nested-looking while loop

This is the complexity-analysis trap interviewers love to probe (see Interview Foundations). The while loop looks like it could make the whole thing O(n²), the same way a naive reading of any nested loop would. But look at what the loop actually does: it only ever pops elements off the stack, and every index is pushed onto the stack exactly once (in the single for loop). Since an index can be popped at most once — after it's popped it's gone for good — the total number of pop operations across the entire run of the algorithm is bounded by n. So total work is: n pushes + at most n pops = O(n) amortized, even though any single iteration of the outer loop could, in the worst case, trigger a long chain of pops (e.g., a strictly decreasing input followed by one huge value). This is the same "amortized analysis" idea as dynamic array resizing — locally expensive, globally cheap.

Values vs. indices — the detail that trips people up

Push indices onto the stack, not values, unless you're certain you'll never need position information. Reasons this matters:

  1. Distance-based answers (Daily Temperatures wants i - j, not a value) are impossible to compute if you only stored values.
  2. Duplicate values are ambiguous — if two elements have the same value, only the index tells you which one you're resolving.
  3. You often need nums[stack[-1]] for comparisons and stack[-1] itself for the final answer — storing the index gives you both (nums[index] is a cheap lookup).

Common variations

  • Circular arrays (Next Greater Element II): conceptually run the array twice by iterating 2n times and indexing with i % n. Only compute answers during the first pass over each index; keep pushing on the second pass so later (wrapped-around) elements can still resolve earlier ones.
  • Span / distance aggregation (Online Stock Span, Car Fleet): instead of storing just an index, store a (value, aggregate) pair, and when you pop, fold the popped aggregate into the new one before pushing.
  • Contribution / counting technique (Sum of Subarray Minimums): for each element, find both its previous smaller and next smaller (or smaller-or-equal, to break ties consistently) boundary via two monotonic-stack passes, then the number of subarrays where that element is the minimum is (i - left) * (right - i). This "count how many windows this element dominates" idea generalizes to a lot of "sum over all subarrays" problems.
  • Histogram / interval expansion (Largest Rectangle in Histogram): use a monotonic increasing stack of indices; when you pop index j because a shorter bar arrived, the rectangle at height heights[j] spans from just after the new stack top to just before the current index — width i - stack[-1] - 1 (or i if the stack is empty). Appending a sentinel 0 to the end of the array lets you flush the whole stack without a second loop.
  • Greedy digit/character removal (Remove K Digits, Remove Duplicate Letters): the stack holds the "result so far"; you pop trailing characters that are worse than the incoming one (as long as you're still allowed to remove more), which greedily builds the smallest/largest valid sequence.

Common pitfalls and interview gotchas

  • Off-by-one on width calculations. In histogram-style problems, whether the width is i - stack[-1] - 1 or i - stack[-1] is the single most common submission bug — draw a small example and count indices explicitly rather than guessing.
  • Strict vs. non-strict comparisons. < vs <= in the pop condition changes how duplicate values are handled and can silently produce wrong answers only on inputs with repeats — always ask "what happens with ties?" before finalizing your condition.
  • Forgetting the leftover stack. After the main loop, indices still on the stack have no valid "next" element — make sure your initialization (-1, 0, etc.) correctly represents "no answer" rather than leaving stale data.
  • Storing values instead of indices when you'll later need positions or need to distinguish duplicate values (see above).
  • Confusing this with a plain stack problem. If the problem doesn't have a "nearest qualifying neighbor" flavor — if it's about nesting or matching instead (balanced parentheses, expression evaluation) — you want the techniques in Stack Simulation, Parsing & Expression Evaluation, not a monotonic invariant.
  • Assuming it only works on numeric arrays. Anything with a well-defined order (heights, prices, temperatures, even lexicographic character order) qualifies.

Worked example: teaching the mechanics without spoiling a listed problem

The problem below — previous greater element — uses the identical template you'll apply to every problem in this subtopic, just with the scan direction and comparison flipped relative to "next greater":

def previous_greater_elements(nums): """ For each index i, find the value of the nearest element to its LEFT that is strictly greater than nums[i]. -1 if none exists. Monotonic DECREASING stack, scanned left to right. """ n = len(nums) result = [-1] * n stack = [] # indices, values strictly decreasing bottom -> top for i in range(n): # Anything <= nums[i] can never be the "previous greater" for # anyone after i either, so it's safe to discard permanently. while stack and nums[stack[-1]] <= nums[i]: stack.pop() if stack: result[i] = nums[stack[-1]] stack.append(i) return result # [10, 4, 2, 20, 40, 12] # -> [-1, 10, 4, -1, -1, 40]

Notice the structure is identical to the generic template: pop while the invariant is violated, read off an answer (this time from the new top of stack, not the popped element — because "previous greater" resolves at push time, not pop time), then push. Once this shape is automatic, adapting it to "next greater," "span," or "histogram width" is a small, mechanical change to the condition and the resolution step — practice noticing which of the two ("resolve on pop" vs. "resolve on push after popping") a given problem needs, since mixing them up is a common source of bugs under interview pressure.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.