Monotonic Stack Explained — Pending Questions, Two Directions, Three Walkthroughs

The monotonic stack is a stack that quietly deletes elements it no longer needs. That's it — one sentence of extra rule on top of the plainest data structure in the toolbox. The rule is what turns a nested loop that looks O(n²) into a two-line proof of O(n), and lets you solve "next greater element" without ever writing a nested loop.

Recognition — when to reach for it

Monotonic stack is the right tool when all three of these hold:

1. You're processing a linear sequence — array, string, stream — and, for each element, you need to know something about the next (or previous) element satisfying a comparison: greater, smaller, greater-or-equal, first taller bar, first colder day.
2. The brute force is O(n²) — for each element, scan forward or backward until you find the answer.
3. The comparison is one-directional: strictly greater, strictly smaller, or a fixed inequality. If the comparison flips depending on context, monotonic stack doesn't apply.

The two questions monotonic stack is built to answer:

• Next greater / smaller element — for each index i, what's the first index j > i where nums[j] beats nums[i] (by whatever comparison)? Answer -1 if none.
• Previous greater / smaller element — same thing, looking backward.

If your problem restates as one of those in the interview whiteboard, the pattern applies.

Mental model — a stack of pending questions

The monotonic stack contains elements whose "next X" hasn't been decided yet. When a new element arrives, ask: does the new element answer any pending questions? If yes, pop those elements and record the answer. If no, push the new element (its own question is now pending).

Two consequences fall out of that framing, and they're the whole technique:

1. The stack contents are always monotone. If the pop condition is "pop when incoming > top", then whatever survives is ≥ the incoming — so the stack is monotonically decreasing (bottom to top). Flip the condition to "pop when incoming < top" and the stack is monotonically increasing. Which direction depends on which "next X" you want.
2. Each element is pushed exactly once and popped at most once. That's O(1) amortised per element, O(n) total, even though the inner while loop looks O(n) in the worst case. This is the source of the "the while inside the for is still O(n)" claim that trips first-time learners.

That's the entire mental model. The templates below just make it explicit.

The two templates

Given a linear scan of nums:

Next greater to the right — monotonic decreasing stack

def next_greater(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []  # indices with pending "next greater"

    for i, num in enumerate(nums):
        # Pop everything the incoming num answers.
        while stack and nums[stack[-1]] < num:
            j = stack.pop()
            result[j] = num
        stack.append(i)

    return result

Stack invariant: nums[stack[0]] >= nums[stack[1]] >= … >= nums[stack[-1]].

Next smaller to the right — monotonic increasing stack

Same shape, flipped comparison:

while stack and nums[stack[-1]] > num:
    ...

Stack invariant flips: nums[stack[0]] <= nums[stack[1]] <= … <= nums[stack[-1]].

The rest of the 2×2 matrix

Direction of scan × pop condition:

A bonus that doesn't cost extra: after the pops in any pass, whatever sits on top of the stack is the previous counterpart for the incoming element. Left-to-right with the "next greater" pop condition gives you both next_greater[popped] (from the pop event) and previous_greater_or_equal[incoming] (from what's still on the stack after pops) in the same pass. Every worked-out monotonic-stack problem is one of those four cells, sometimes two at once.

Indices, not values. Store indices in the stack, not values. You almost always need to know how far apart the elements are — days until warmer, bars separating a rectangle — and index arithmetic is impossible if you've thrown the indices away.

Walkthrough 1 — LeetCode 496, Next Greater Element I

Given two arrays nums1 and nums2, where nums1 is a subset of nums2 and both have unique values, return an array where answer[i] is the next greater element of nums1[i] in nums2, or -1 if none exists.

Recognition. "Next greater" ✓. Unique values (lets us use values as dictionary keys). Brute force is O(n₁ × n₂) — for each nums1[i], scan forward in nums2. Monotonic stack collapses nums2's side to O(n₂).

Approach. Precompute next_greater[value] for every element in nums2 with a decreasing monotonic stack, then look up each nums1[i].

def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
    next_greater: dict[int, int] = {}
    stack: list[int] = []

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)
    # Anything left on the stack has no next greater — dict absence == -1.

    return [next_greater.get(x, -1) for x in nums1]

Trace nums2 = [1, 3, 4, 2], nums1 = [4, 1, 2].

next_greater = {1: 3, 3: 4}. For nums1 = [4, 1, 2], we get [-1, 3, -1].

Notice each nums2 value was pushed exactly once and popped at most once — that's the O(n) accounting.

Walkthrough 2 — LeetCode 739, Daily Temperatures

Given an array of daily temperatures, return an array answer where answer[i] is the number of days you have to wait until a warmer temperature. If none exists, answer[i] == 0.

Recognition. "Next greater" ✓. Need the distance to the answer, not the answer itself — so store indices on the stack, not values. Brute force is O(n²).

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack: list[int] = []  # indices of days with pending "warmer day"

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)

    return result

Trace temperatures = [73, 74, 75, 71, 69, 72, 76, 73].

Result: [1, 1, 4, 2, 1, 1, 0, 0]. Indices 6 and 7 stay on the stack forever — no warmer day arrives — so their result stays 0.

The key micro-observation: after step 5, the stack is [2, 5], which is indices with temperatures [75, 72] — monotonically decreasing. That's the invariant surviving through every push.

Walkthrough 3 — LeetCode 84, Largest Rectangle in Histogram

Given an array of bar heights, find the area of the largest rectangle that fits under the histogram.

This is the boss level. The trick is to pick the right "pending question" — and it isn't next-greater.

The framing. For each bar heights[i], what's the largest rectangle where heights[i] is the shortest bar? The rectangle extends left until it hits a bar shorter than heights[i], and right until it hits one shorter. If we compute that quantity for every bar and take the max, we've solved it.

Now the recognition kicks in: for each bar, we need the previous smaller bar's index and the next smaller bar's index. That's two calls to the monotonic-stack machinery, but you can weave them into a single scan.

The algorithm. Left-to-right, monotonically increasing stack of indices. When a shorter bar arrives, pop each taller bar and compute its rectangle — the incoming bar is that bar's "next smaller" (right edge), and whatever sits on the stack after the pop is that bar's "previous smaller" (left edge). Add a sentinel 0 at the end so the stack drains cleanly.

def largestRectangleArea(heights: list[int]) -> int:
    best = 0
    stack: list[int] = []
    # Sentinel at the right forces every remaining index to be popped.
    heights = heights + [0]

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            # Left edge is the new top of stack (or -1 if empty);
            # right edge is i. Width excludes both edges.
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        stack.append(i)

    return best

Trace heights = [2, 1, 5, 6, 2, 3] (sentinel makes it [2, 1, 5, 6, 2, 3, 0]).

Answer: 10 (the 5+6 pair popped at step 4 forms a 2 × 5 = 10 rectangle across indices 2 and 3).

Two details worth naming out loud:

• The sentinel (heights + [0]) is what makes the stack drain. Without it, indices 1, 4, 5 would sit on the stack forever and never contribute their rectangles. Any sentinel value shorter than every real bar works; 0 is the cheapest.
• The width formula (i - stack[-1] - 1 or i if the stack is empty) is where every implementation of LC 84 mis-types itself once. When stack is empty after the pop, the popped bar was the shortest bar in the whole prefix so far, so the rectangle extends all the way to index -1 (imaginary sentinel on the left). That's why the width is i - (-1) - 1 = i.

When monotonic stack is not the tool

Same recognition checklist, failure modes made explicit:

• The comparison flips per-element. Monotonic stack needs a fixed inequality (always > or always <). If some elements want "next greater" and others want "next smaller", you're looking at two separate scans.
• You need aggregate info about the region, not just the boundary. Sums, averages, or counts across the range between elements often want prefix sums or segment trees — monotonic stack gives you boundary indices, not summarised content.
• You need pairs, not neighbours. LC 42 Trapping Rain Water can be solved with a monotonic stack, but two-pointer is the cleaner O(1)-space solution. If the problem naturally reads as "pick two indices", check two-pointer first.
• You don't actually need the answer for every element. If you only need "the maximum next-greater across the array" or one specific query, a linear scan may be simpler and cheaper in constant factors.

How the Algotrek tutor would prompt you here

When a learner opens a monotonic-stack problem on Algotrek, the tutor doesn't reveal the template. It asks three questions, and only advances when each is answered in one sentence:

1. "For each element, what's the pending question?" — Forces the learner to name it. "The number of days until a warmer temperature." "The nearest shorter bar to the right." "The largest rectangle with this bar as the shortest." Naming the pending question is what turns an intimidating problem into a decorated next_greater call.
2. "When a new element arrives, whose question does it answer?" — This is the pop condition. If the answer is "everyone shorter than me", the stack is monotonically decreasing (top is smallest of what's left). If "everyone taller than me", monotonically increasing. Pin this down and the direction falls out.
3. "Do you need the answer's value, its index, or the distance between them?" — This is what tells you whether the stack stores values or indices. LC 496 stores values because the answer is a value. LC 739 stores indices because the answer is a distance. LC 84 stores indices because the answer needs three indices at once.

Answer all three and the template is a copy-paste with the comparison flipped. Try the Daily Temperatures lesson on Algotrek to see the prompt-then-reveal flow on the friendliest interview-classic monotonic-stack problem — the tutor walks the "what haven't we finished yet?" framing before it hands over any code.

Where to go next

• LC 503, Next Greater Element II. Circular variant of LC 496. Concatenate the array with itself (conceptually) and run the same scan modulo n. A great sanity check that you understand the technique doesn't care about the array's shape — only its scan order.
• LC 42, Trapping Rain Water. The monotonic-stack solution is the didactic one; the two-pointer solution is the elegant one. Solving it both ways is the fastest way to internalise "same problem, different invariant" — the meta-skill the whole series is aimed at.
• LC 907, Sum of Subarray Minimums. Uses previous_smaller and next_smaller on the same array (both in one scan). If you can name the contribution of each element to the total sum, this problem folds into two O(n) passes.
• LC 85, Maximal Rectangle. LC 84 lifted into 2D. Run LC 84 on every row of a histogram-style projection. If LC 84 clicked, this becomes an O(n × m) reduction rather than a new technique.

Cross-reference the sliding-window, two-pointer, and binary-search posts. All four techniques answer the same meta-question — what work can I prove I don't need to do? — but they answer it with different invariants: a contiguous region for sliding window, a converging pair for two-pointer, a bisectable space for binary search, a stack of pending questions for monotonic stack. Recognising which invariant the problem hands you is the interview skill; the templates are how you cash it in.

For the "each element pushed once and popped at most once → O(n)" argument at the heart of this post, the Big-O cheat sheet's dynamic-array-and-stack row is the line item that makes the amortised claim rigorous.