The Monotonic Stack: Like Gandalf's Staff for Array Problems

The Quest Begins (The "Why")

Honestly, I still remember the first time I stared at the Daily Temperatures problem on LeetCode and felt like I was trying to crack a vault with a toothpick. The brute‑force solution — two nested loops, checking every future day for a warmer temperature — was simple to write, but it timed out on the larger test cases. I spent an hour tweaking loops, adding early breaks, and even trying to memoize results, only to watch the same red “Time Limit Exceeded” banner flash again.

I was frustrated, but more than that, I was curious. Why did this problem feel so repetitive? Every element seemed to be asking the same question: “What’s the next greater value to my right?” If I could answer that for each index in a single pass, the whole thing would collapse into O(n). That’s when I remembered a weird little data structure I’d seen in a textbook — the monotonic stack — and realized it might be the magic wand I needed.

The Revelation (The Insight)

Here’s the thing: a monotonic stack isn’t just a stack with a funny name; it’s a way to capture relationships between elements without ever looking backward more than once.

Imagine you’re walking through a line of people sorted by height, and you want to know, for each person, who is the first taller person standing ahead of them. If you keep a stack of people whose heights are strictly decreasing as you move from left to right, then whenever you see a new person taller than the one on top of the stack, you’ve just found the answer for that stacked person: the current person is their “next greater.” You pop them off, record the distance, and keep going. Because each index is pushed once and popped at most once, the total work is linear.

The same idea works for “next smaller,” “previous greater,” or any problem where you need the nearest element that satisfies a monotonic condition. The stack does the heavy lifting of remembering candidates that could still be relevant, discarding the ones that are already dominated by a newer element. It’s like having Gandalf’s staff: you point it at the array, and the staff instantly reveals the hidden order without you having to swing a sword at every pair.

Wielding the Power (Code & Examples)

Before: The Brute‑Force Struggle

def daily_temperatures_bruteforce(temps):
    n = len(temps)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temps[j]temps[j] > temps[i]:
                answer[i] = j - i
                break
    return answer

Ouch — O(n²) time, O(1) extra space. It works on tiny inputs, but any realistic test set makes it crawl.

After: Monotonic Stack to the Rescue

def daily_temperatures(temps):
    n = len(temps)
    answer = [0] * n
    stack = []               # will store indices with decreasing temperatures

    for i, t in enumerate(temps):
        # While current temp breaks the decreasing order,
        # we have found the next greater for the stacked indices.
        while stack and temps[stack[-1]] < t:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)

    # Remaining indices have no warmer day; answer stays 0.
    return answer

Why it’s O(n): each index is pushed onto stack once and popped at most once. The inner while loop may look like it could be nested, but the total number of iterations across the whole run is bounded by n. Space is O(n) in the worst case (a strictly decreasing temperature series).

Another Classic: Largest Rectangle in Histogram

Same principle, just flipped: we need the previous smaller and next smaller for each bar.

def largest_rectangle_area(heights):
    stack = []          # 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 current index i minus index of new top minus 1
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Again, each bar is pushed and popped once → O(n) time, O(n) space.

Traps to Avoid on the Quest

• Equality handling: If you need “next greater or equal,” change the comparison to <= (or >= for smaller). Mixing up strict vs. non‑strict breaks the invariant.
• Direction confusion: Decide whether you’re scanning left‑to‑right for next greater or right‑to‑left for previous greater, and keep the stack order consistent.
• Cleaning up: After the main loop, don’t forget to pop the remaining elements and assign their answer (often 0 or a default).

Why This New Power Matters

Once you internalize the monotonic stack trick, a whole family of interview‑favorite problems becomes trivial:

• Daily Temperatures / Next Greater Element
• Largest Rectangle in Histogram
• Sum of Subarray Minimums
• Maximum Width Ramp
• Trapping Rain Water

You’ll stop writing those dreadful double‑loops and start spotting the pattern: “I need the nearest element that beats (or is beaten by) the current one under a monotonic condition.” It’s like gaining a new spell slot in your coding repertoire — suddenly, the boss fights feel manageable.

And the best part? The intuition transfers beyond arrays. Monotonic stacks appear in parsing (e.g., evaluating expressions), in graph algorithms (like finding next greater node in a tree), and even in computational geometry. Once you see the pattern, you’ll start spotting it everywhere.

Your Turn – The Next Challenge

Here’s a fun quest for you: Solve “Sum of Subarray Minimums” (LeetCode 907) using a monotonic stack. Try to derive why each element contributes left * right * value to the total, where left is the distance to the previous strictly smaller element and right is the distance to the next smaller-or-equal element.

Drop your solution or any questions in the comments — let’s see who can wield the staff most elegantly! Happy stacking!