Monotonic Stack: The Pattern Nobody Taught You

TL;DR: A monotonic stack is a plain stack with one house rule: elements must stay in sorted order, and any newcomer that violates the rule pops elements until order is restored. That single rule answers the entire "next greater / next smaller / previous greater / previous smaller" family in O(n), plus everything built on it (Daily Temperatures, Largest Rectangle in Histogram, stock spans, ocean views). It's also the pattern with the strangest history: nearly absent from interviews a decade ago, now a fixture at every major company, and still missing from most older prep lists. If your list predates ~2019, this is your biggest blind spot.

This is the fifth deep dive in our pattern series, after sliding window, two pointers, fast & slow pointers, and merge intervals. Monotonic stack earns its subtitle honestly: it rose from obscurity to ubiquity within a few interview generations, which means a whole cohort of engineers prepped on older material (including Blind 75) simply never installed it. Interviewers know that, and they use it.

The tell: how to recognize a monotonic stack problem

You should suspect this pattern when the problem asks, for each element, about its nearest neighbor in one direction that beats it:

• "next greater element" / "previous smaller element"
• "how many days until a warmer temperature"
• "how far can this element see before something taller blocks it"
• "largest rectangle in a histogram" / "maximal rectangle in a grid"
• "span of stock prices" / remove digits to make the smallest number

The unifying shape: a question that relates each element to the closest element (left or right) that is greater or smaller than it. The brute force compares every element with everything after it, O(n²). The moment you catch yourself writing that nested rescan, stop; this pattern exists to delete it.

The one insight the whole pattern rests on

Here's the sentence to say in an interview, because it is the pattern: when a new element arrives, it answers the question for every waiting element it beats.

Walk through it with temperatures. You're scanning left to right, and several earlier days are still waiting for a warmer day. Those waiting days, notice, are always in decreasing order (if day A were warmer than a later waiting day B, then B... wait, no: if an earlier day were cooler than a later one, the later one would have already answered it). So the waiting room is a stack in decreasing order. When today's temperature arrives, it resolves every waiting day cooler than it: pop them, record their answers, then join the waiting room yourself. Each day enters the room once and leaves once, so the entire scan is O(n) no matter how many pops any single step triggers. That amortized argument is the second thing to say out loud; interviewers grade it like the discard argument in two pointers.

The template

Daily Temperatures (LeetCode 739) is the canonical form. Store indices, keep the stack's temperatures decreasing:

def daily_temperatures(temps):
    stack = []                          # indices; temps[stack] is decreasing
    answer = [0] * len(temps)
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()             # today resolves day j
            answer[j] = i - j           # distance = the wait
        stack.append(i)                 # today starts waiting
    return answer

Every monotonic stack solution is this loop with different bookkeeping in the pop. The elements left on the stack at the end are the ones whose question has no answer (no warmer day ever comes); their zeros are already in place here, but in other problems you must handle the leftovers explicitly.

The compass: which stack for which question

Candidates memorize "decreasing stack" from one problem and then flounder when the question flips. Don't memorize instances; use the compass:

• Next greater (to the right) → maintain a decreasing stack; the newcomer pops everyone it beats, and each popped element's answer is the newcomer.
• Next smaller → same machinery, increasing stack.
• Previous greater / previous smaller → the answer isn't found by popping; it's whoever remains on top of the stack when you push. Same scan, read a different moment.

Two lines of reasoning replace four memorized templates: the pops answer "next", the top-at-push answers "previous", and the stack's direction is the opposite of the comparison you're asking about.

The escalations interviewers actually reach for

• Next Greater Element II (circular array): run the same scan twice (or loop 2n with modulo). Tests whether you understand the template or copied it.
• Buildings With an Ocean View: "which buildings see the ocean" is "which elements have no greater element to their right", the same question wearing real estate. A Meta favorite, and a preview of our Meta coding interview guide.
• Remove K Digits: build the smallest number by keeping an increasing stack and budgeting your pops. The pattern's greedy crossover, and the first place students realize the stack can represent "the best prefix so far."
• Largest Rectangle in Histogram: the boss fight. Each bar's maximal rectangle is bounded by its nearest smaller neighbor on each side, which is exactly two monotonic stack questions fused into one pass. If you can narrate why popping a bar computes its full rectangle, you've mastered the pattern.
• Sum of Subarray Minimums (stretch): counts each element's contribution as the minimum across all subarrays where it rules, using both nearest-smaller distances. The contribution trick generalizes to a family of hard problems.

Want each escalation taught step by step? The monotonic stack chapter of Grokking the Coding Interview builds from Next Greater Element through Largest Rectangle with visual stack traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The three mistakes that sink candidates

1. The strictness bug (< vs <=). Whether equal elements pop each other decides correctness in problems with duplicates. In Sum of Subarray Minimums, using strict comparison on both sides double-counts subarrays with tied minimums; the standard fix is strict on one side, non-strict on the other. Whenever the input can contain duplicates, decide the tie-break before coding and say why.

2. Storing values when the question needs positions. Daily Temperatures asks for a distance, so the stack must hold indices, not temperatures. The general rule: store indices always; you can look up a value from an index in O(1), but you can't recover a position from a value. It costs nothing and prevents the rewrite.

3. Forgetting the leftovers. Elements still on the stack at the end have no "next greater" (answer 0, -1, or "visible", depending on the problem), and in Largest Rectangle the leftover bars still need their rectangles computed (the clean trick: append a sentinel bar of height 0 to flush the stack). A solution that works on the sample and fails on a strictly increasing input almost always died here.

Practice ladder

In order; each rung adds one wrinkle.

1. Next Greater Element I (E): the raw template on a toy problem.
2. Daily Temperatures (M): the canonical form with distances; rehearse the amortized O(n) argument.
3. Next Greater Element II (M): the circular variant.
4. Buildings With an Ocean View (M): the "no greater to the right" reframing; high-frequency at Meta.
5. Online Stock Span (M): the "previous greater" direction, streamed.
6. Remove K Digits (M): the greedy crossover.
7. Largest Rectangle in Histogram (H): the boss fight; both directions at once.
8. Stretch goal: Sum of Subarray Minimums (M/H): the contribution technique, plus the strictness tie-break in the wild.

Then write the tell in your own words ("I should suspect a monotonic stack when ___") and move on. Recognition, not volume, is the skill, and this pattern's tell is one of the easiest to spot once named.

The takeaway

One house rule (keep the stack sorted, pop violators), one insight (each newcomer answers everyone it beats), one argument (everyone enters and leaves once, so O(n)), and one compass (pops answer "next", the top at push answers "previous"). That's the entire pattern that separates candidates who prepped on current material from candidates who prepped on 2018's. It's the highest-leverage single pattern to add if your list predates it, and the full map of where it sits among the other 41 is in the complete pattern guide. Next in the series: Top 'K' Elements, where a heap of size k quietly replaces a full sort.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79. Short on time? Grokking 75 includes the essential monotonic stack problems in its 6-week plan.

FAQs

What is a monotonic stack in simple terms? A stack that keeps its elements in sorted order (increasing or decreasing) by popping any elements the newcomer beats before it's pushed. Those pops are the payoff: each one resolves a "nearest greater/smaller element" question in O(1) amortized time.

When do I use an increasing vs a decreasing stack? Opposite of the comparison you're asking about: finding the next greater element needs a decreasing stack (so greater newcomers trigger pops), and the next smaller element needs an increasing stack. For "previous" variants, the answer is whatever sits on top of the stack at the moment you push.

Why is a monotonic stack O(n) if there's a while loop inside the for loop? Amortized analysis: every element is pushed exactly once and popped at most once across the whole scan, so total stack operations are at most 2n regardless of how the pops cluster. It's the same argument shape as sliding window's shrink loop, and stating it earns real interview points.

Is the monotonic stack really asked at FAANG companies? Constantly, and increasingly: Daily Temperatures and Next Greater Element are standard screens, Buildings With an Ocean View is a Meta regular, and Largest Rectangle in Histogram is a classic hard at Google and Amazon. Its rise since ~2019 is exactly why older prep lists underweight it.

How is monotonic stack different from sliding window or two pointers? All three exploit "never revisit" structure for O(n), but they track different things: sliding window maintains aggregate state over a contiguous range, two pointers reasons about elements at two positions, and a monotonic stack maintains an ordered history of unresolved elements. If the question is "nearest element that beats me," it's the stack.