Monotonic Stacks

The mental model: a waiting room

Think of the stack as a waiting room for elements that haven't found their answer yet. Every element walks in, sits down, and waits for the first element that is bigger than it (for next-greater problems). When a new arrival is bigger than someone already seated, those people jump up — they've found their answer, and it's the new arrival. The new arrival sits down and waits its turn.

That image captures why the algorithm is O(n). People enter the room exactly once and leave exactly once. You can't leave without having entered. Over n elements, there are at most n entries and n exits — 2n operations total, O(n).

The alternative — for every element, scan right until you find a bigger one — is O(n²). You're doing redundant work: asking the same "is there something bigger to your right?" question over and over. The stack eliminates that by remembering, for each unresolved element, exactly what it needs.

The pop-while loop: the skeleton

Every monotonic stack solution centers on this same structure:

stack = []  # monotonic decreasing (for next-greater problems)

for i, val in enumerate(arr):
    # Pop everything smaller than val — they've found their answer
    while stack and arr[stack[-1]] < val:
        idx = stack.pop()
        result[idx] = val   # val is the next greater element for arr[idx]
    stack.append(i)         # push index, not value (need position for width later)

# Anything still in the stack has no next greater element
while stack:
    result[stack.pop()] = -1

A few things to notice:

1. We store indices, not values. You can always get the value with arr[idx], but you can't recover the index from the value. And for any problem involving width or distance, you need indices.
2. The inner while-loop pops, not just one element. A single new arrival can trigger multiple pops if it beats several queued-up elements in one shot.
3. The cleanup at the end. Elements left in the stack when you finish scanning never found a next-greater element — fill their result with -1 (or 0, or infinity, depending on the problem).

Worked problem 1: Next Greater Element (the warmup)

Given [2, 1, 5, 3, 4], for each element find the first element to its right that is larger. Result: [5, 5, -1, 4, -1].

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # indices, monotonic decreasing by arr[i]

    for i in range(n):
        # While top of stack is smaller than current, current is their answer
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result  # stack leftovers keep their -1 default

Trace through [2, 1, 5, 3, 4]:

i	val	stack (indices)	pops	result
0	2	[0]	—	[-1,-1,-1,-1,-1]
1	1	[0,1]	—	[-1,-1,-1,-1,-1]
2	5	[] → [2]	pop 1 (ans=5), pop 0 (ans=5)	[5,5,-1,-1,-1]
3	3	[2,3]	—	[5,5,-1,-1,-1]
4	4	[2,3,4] → [2,4]	pop 3 (ans=4)	[5,5,-1,4,-1]

After the scan, indices 2 and 4 are still in the stack. Their result stays -1.

Time: O(n). Space: O(n) for the stack.

Worked problem 2: Daily Temperatures

This is next-greater-element with a twist: instead of the value, return the number of days until a warmer temperature.

[73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]

The distance comes from subtracting indices — which is exactly why storing indices matters.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n          # 0 means "no warmer day"
    stack = []                # indices, monotonic decreasing by temperature

    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            result[idx] = i - idx    # days to wait = current index minus that day's index
        stack.append(i)

    return result

The only change from the template is result[idx] = i - idx instead of result[idx] = arr[i]. Same structure, different output. This is the cleanest example of the pattern because the problem maps directly to it — no preprocessing, no reversal, no edge case gymnastics.

{ "type": "stack", "variant": "stack", "title": "Stack stores unresolved indices (daily temperatures)", "data": [5, 3, 2] }

Think of those stack values as indices [5, 3, 2] — positions 5, 3, and 2 in the temperatures array are still waiting for a warmer day. When index 6 (76°) arrives and it's hotter than everything there, all three pop: their wait was 6-5=1, 6-3=3, 6-2=4 days. One sweep through the entire array handled all of them.

Worked problem 3: Largest Rectangle in Histogram

This is where monotonic stacks earn their reputation. Given an array of bar heights, find the largest rectangle you can form.

[2, 1, 5, 6, 2, 3] → answer is 10 (the 5×2 rectangle using bars 2 and 3).

The key insight: for each bar, the largest rectangle that uses that bar's full height extends left and right until it hits a bar shorter than itself. The "nearest shorter bar to the left" and "nearest shorter bar to the right" together define the width.

This is a next-smaller-element problem — so we flip to a monotonic increasing stack (triggers pops when a smaller element arrives).

def largest_rectangle_histogram(heights):
    stack = []      # indices, monotonic increasing by height
    max_area = 0
    heights = heights + [0]   # sentinel: force all remaining bars to pop at the end

    for i, h in enumerate(heights):
        # Current bar is shorter — pop bars that can't extend this far right
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # Width: from the new stack top (exclusive) to current position i (exclusive)
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

The tricky part is the width calculation. When you pop index j with height heights[j]:

• The right boundary is i (the current bar that triggered the pop — it's shorter).
• The left boundary is whatever is now on top of the stack after the pop, call it k. Everything between k and i is at least as tall as heights[j], so the rectangle spans from k+1 to i-1.
• Width = i - k - 1.
• If the stack is empty after the pop, there's nothing shorter to the left — the rectangle spans from 0 to i-1, so width = i.

The sentinel 0 at the end forces every remaining bar to pop cleanly without a special post-loop case.

flowchart LR
    subgraph "heights = [2, 1, 5, 6, 2, 3, 0]"
        direction LR
        B0["[0] h=2"]
        B1["[1] h=1"]
        B2["[2] h=5"]
        B3["[3] h=6"]
        B4["[4] h=2"]
        B5["[5] h=3"]
        B6["[6] h=0 (sentinel)"]
    end
    B4 -->|"triggers pop of [3](h=6) → area=6×1=6"| R1["area 6"]
    B4 -->|"triggers pop of [2](h=5) → area=5×2=10"| R2["area 10 ✓"]
    B6 -->|"forces remaining pops"| R3["remaining cleanup"]
    style R2 fill:#00ff9d,color:#0a0a0f
    style B4 fill:#7c5cff,color:#fff

Time: O(n) — same amortized argument. Each bar is pushed once, popped once. Space: O(n).

Worked problem 4: Trapping Rain Water

One of the most famous hard problems in interview circuits, and it has a clean monotonic stack solution that people often miss.

Given [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], how many units of water are trapped?

The idea: water is trapped in valleys — between a left wall and a right wall, above the valley floor. When a taller bar arrives and causes a pop, the popped bar is the valley floor. The left wall is the new stack top; the right wall is the current bar.

def trap_rain_water(height):
    stack = []      # indices, monotonic decreasing by height
    water = 0

    for i in range(len(height)):
        while stack and height[stack[-1]] < height[i]:
            bottom_idx = stack.pop()        # the valley floor
            if not stack:
                break                       # no left wall — no water
            left_idx = stack[-1]            # left wall
            right_idx = i                  # right wall

            h = min(height[left_idx], height[right_idx]) - height[bottom_idx]
            w = right_idx - left_idx - 1
            water += h * w

        stack.append(i)

    return water

Notice the difference from the histogram problem: here we're popping on strictly less than (smaller triggers pops = decreasing stack), because water fills valleys and we pop floors. In the histogram we popped on greater than (larger triggers pops = increasing stack), because we need the nearest shorter bar.

Both use the same pop-while structure. The direction flips based on what you're hunting.

The tell: how to spot this pattern

A problem probably wants a monotonic stack when it asks for something like:

• "For each element, find the nearest element to the left/right that is greater/smaller."
• "Find the maximum rectangle / area / trapped water" (hidden next-smaller variant).
• "How many days until the temperature is warmer?" (next-greater distance).
• Anything where you're scanning once and for each position asking a question about its neighborhood.

The dead giveaway is the phrase "nearest" or "next" combined with a comparison. If a brute force would be O(n²) because for every element you scan outward until you find something, the monotonic stack makes it O(n) by maintaining exactly the candidates you need.

Compare to sliding window: that technique also scans in O(n) with a similar "maintain a useful data structure as you go" flavor, but sliding window is about aggregate values over a range (max, sum, distinct count) with a fixed or variable window size. Monotonic stack is about per-element nearest-neighbor comparisons with no window constraint. If your problem has a window size parameter, look at sliding window first — you might want a deque, not a stack.

The monotonic increasing vs. decreasing choice

This trips people up. Here's the rule, stated clearly:

I want to find...	Stack order	Pop when...
Next greater element (to the right)	Decreasing (bottom→top)	new_val > stack_top
Next smaller element (to the right)	Increasing (bottom→top)	new_val < stack_top
Previous greater element (to the left)	Scan right-to-left, decreasing stack	same trigger
Previous smaller element (to the left)	Scan right-to-left, increasing stack	same trigger

The logic: you maintain the property that the stack is never the answer to any currently waiting element. So for a decreasing stack waiting for "next greater," every element in the stack is smaller than or equal to everything below it — which means nothing in the stack is the next greater element for anything else in the stack. The moment a larger element arrives and breaks that property, it becomes the answer for everything it's larger than.

If you mix these up under interview pressure, just ask yourself: "what causes a pop?" The popping trigger is the answer type you're computing. If popping happens when the new element is larger, you're computing next-greater. If popping happens when the new element is smaller, you're computing next-smaller.

Pitfalls people actually hit

Storing values instead of indices. You'll hit this the first time you try the histogram problem and realize you have no idea what width is. Store indices. Always. You can get the value back with arr[idx]; you cannot recover the index from the value.

Off-by-one in width calculations. For the histogram, the width formula i - stack[-1] - 1 is right_exclusive - left_exclusive - 1. Draw it out for a 3-bar example and count squares. The -1 makes sense when you realize both boundaries are excluded. For rain water, the same formula applies.

Forgetting the sentinel. In the histogram, appending a 0 to the heights array forces all remaining bars to pop and be evaluated. Without it you need a second loop after the main scan to handle bars still in the stack. The sentinel is cleaner. For rain water, the loop structure is slightly different and you handle the empty-stack case with a break instead.

Using <= vs < in the pop condition. For next-greater with duplicates, you usually want < (strict) so that equal elements pop each other rather than block each other. For the histogram, the choice affects whether adjacent bars of equal height get merged — but the area calculation is still correct either way. When in doubt, trace through a [5, 5] example and see which version gives the right answer.

Thinking the inner loop makes it O(n²). The amortized argument kills this fear. Write it out: over n iterations, the total number of pushes is n (each element pushed once), and total pops ≤ n (you can't pop what wasn't pushed). Total stack operations: 2n. The outer loop is n. Grand total: 3n. Still O(n).

When NOT to use a monotonic stack

The monotonic stack is not a universal hammer. Skip it when:

• You need a sorted order you can query repeatedly. A monotonic stack is consumed as it answers. If you need to ask "what's the nearest greater element for element X" after the fact, without a fresh scan, you want a sorted structure like a balanced BST or a binary search tree.
• You need the nearest greater element within a sliding window. That is the deque-based sliding window maximum — same monotonic idea, but you also evict elements that age out of the window from the front. The deque is the right tool; a plain stack loses track of positions.
• The comparison is two-dimensional or involves multiple conditions. Pure monotonic stack gives you one ordering. If you need the nearest element that is both larger AND to the left of some constraint, you'll likely need something more structured.
• n is tiny. An O(n²) nested scan is perfectly fine for n < 100 and sometimes clearer to a reviewer. Don't over-engineer.

The monotonic stack lives in a sweet spot: array problems, single scan, per-element nearest-neighbor queries. When your problem has that exact shape, nothing beats it for elegance and speed.

Complexity

Operation	Time	Space	Note
Build next-greater/smaller array	O(n)	O(n)	amortized — each element pushed and popped once
Largest rectangle in histogram	O(n)	O(n)	sentinel trick avoids post-loop cleanup
Trapping rain water	O(n)	O(n)	same pop-while structure, different accumulation

The space is O(n) for the stack itself, which in the worst case (a perfectly sorted array) holds all n elements before anyone pops. The result array is also O(n) but that is output space you'd pay regardless.

For problems where you want O(1) space, there are two-pointer solutions to Trapping Rain Water and some next-greater variants — but they're harder to generalize. The stack solution is the one to internalize and reach for first.