Monotonic Stack: The Matrix of Array Problems

The Quest Begins (The "Why")

I still remember the first time I faced the “Next Greater Element” interview question. The array looked innocent enough, but every brute‑force attempt felt like I was hammering a nail with a sponge—O(n²) time, nested loops, and a sinking feeling that I was missing something elegant. I spent an hour sketching out the problem on a whiteboard, muttering, “There has to be a way to look ahead without looking back every single time.”

That frustration is a rite of passage for many developers. We’re taught to think in terms of scanning left‑to‑right, but some array puzzles scream for a different perspective: we need to remember what we’ve seen in a way that lets us answer questions about the future elements instantly. Enter the monotonic stack—a deceptively simple data structure that turns those scary “look‑ahead” problems into straight‑line walks.

The Revelation (The Insight)

So what’s the secret sauce? A monotonic stack is just a stack that maintains its elements in strictly increasing or strictly decreasing order. Why does that help?

Consider the Next Greater Element problem: for each index i, we want the first element to its right that’s larger than arr[i]. If we walk from left to right and keep a stack of indices whose next greater element we haven’t found yet, the stack will naturally be decreasing in value.

Why decreasing? Imagine the stack holds indices [i₁, i₂, …, i_k] where arr[i₁] > arr[i₂] > … > arr[i_k]. When we encounter a new value arr[j], any element on the stack that is smaller than arr[j] has just found its next greater element—namely arr[j]. We pop those indices, record the answer, and stop when we hit a value that’s not smaller (or the stack empties). Then we push j onto the stack.

Because each index is pushed once and popped at most once, the total work is linear: O(n). No nested loops, no repeated scans—just a single pass with a stack that does the heavy lifting.

The same invariant works for other “first bigger/smaller to the left/right” problems: largest rectangle in a histogram, trapping rain water, daily temperatures, etc. The stack is the memory that lets us answer “what’s the next element that breaks the monotonicity?” in constant time per element.

Wielding the Power (Code & Examples)

Let’s see the theory in action with two classic interview puzzles. I’ll write the snippets in Python, but the idea translates directly to any language.

1. Next Greater Element (NGE)

Brute‑force (the struggle):

def next_greater_brute(arr):
    n = len(arr)
    res = [-1] * n
    for i in range(n):
        for j in range(i+1, n):
            if arr[j] > arr[i]:
                res[i] = arr[j]
                break
    return res

O(n²) time, O(1) extra space (ignoring output).

Monotonic stack (the victory):

def next_greater(arr):
    n = len(arr)
    res = [-1] * n
    stack = []               # will store indices, decreasing values

    for i, value in enumerate(arr):
        # Resolve indices waiting for a greater element
        while stack and arr[stack[-1]] < value:
            idx = stack.pop()
            res[idx] = value
        stack.append(i)

    return res

Why it works:

• The stack always holds indices whose NGE hasn’t been seen yet.
• When arr[i] is larger than the stack’s top, it’s the NGE for that top element.
• Each index is pushed once, popped once → O(n) time, O(n) worst‑case space (the stack).

Common trap: Forgetting to use <= vs <. If you want the strictly greater element, use <. Using <= would incorrectly treat equal values as NGEs, which fails on inputs like [5,5,5].

2. Largest Rectangle in a Histogram

Given heights of bars, find the maximal rectangle area.

Brute‑force: For each bar, expand left/right until you hit a shorter bar → O(n²).

Monotonic stack solution:

def largest_rectangle(heights):
    stack = []          # indices of increasing heights
    max_area = 0
    # Append a sentinel height 0 to flush the stack at the end
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # width is i if stack empty else distance to previous smaller
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Why it works:

• The stack stores indices of bars in non‑decreasing height order.
• When we see a bar lower than the stack’s top, we know the top bar can’t extend further right; its maximal width is bounded by the current index and the new top of the stack (the previous smaller bar).
• Each bar is pushed and popped once → O(n) time, O(n) space.

Typical mistake: Not adding the sentinel 0 (or a final cleanup loop) leaves bars stuck in the stack, causing missed areas.

Why This New Power Matters

Mastering the monotonic stack feels like unlocking a new spell in your developer’s grimoire. Suddenly, problems that once looked like nested‑loop nightmares melt into clean, linear passes. You’ll start spotting the pattern everywhere: “I need the next bigger/smaller element,” “I need the previous smaller/larger,” “I need to know how far I can stretch before hitting a lower value.”

Beyond interviews, this technique powers real‑world utilities—stock span calculations, histogram‑based image processing, even certain parsing algorithms. The beauty is that the invariant (monotonic order) does the bookkeeping for you; you just focus on the what (when to pop, when to push).

So next time you stare at an array and feel that familiar dread, ask yourself: Can I maintain a monotonic property while scanning? If the answer is yes, you’ve just found your O(n) shortcut.

Your Turn

Here’s a quick challenge to flex your new muscle: Daily Temperatures (LeetCode 739). Given an array T of daily temperatures, return an array where each element tells how many days you’d have to wait for a warmer temperature. If no warmer day exists, put 0.

Try solving it with a monotonic decreasing stack, then compare your solution to the brute‑force version. Share your approach in the comments—let’s see who can devise the most elegant twist!

Happy coding, and may your stacks stay perfectly monotonic! 🚀