Monotonic Stack: The Matrix of Array Problems

The Quest Begins (The “Why”)

Ever spent an hour wrestling with a brute‑force solution that felt like you were trying to break through a concrete wall with a toothpick? I remember the first time I saw the “Next Greater Element” problem on a coding interview. The obvious answer? For each item, scan everything to its right until you find a bigger number. O(n²) time, and my brain started to feel like Neo dodging bullets in slow motion—except I wasn’t dodging, I was getting hit.

That frustration lit a fire. I needed a trick that could look ahead without re‑scanning the same elements over and over. Something that could remember useful information as we walked through the array once, and discard the rest. Enter the monotonic stack—a data structure that turned my O(n²) nightmare into a clean O(n) victory.

The Revelation (The Insight)

So what’s the secret sauce? A monotonic stack is just a stack that keeps its elements in either strictly increasing or strictly decreasing order. When we push a new value, we pop off anything that would break that order. Why does that help? Because each pop tells us that the current element is the “next greater” (or “next smaller”, depending on the direction) for the element we just removed. And crucially, each array element is pushed at most once and popped at most once—so the total work stays linear.

Think of it like assembling a team for a raid. You line up your allies by strength. When a stronger ally shows up, you send the weaker ones back to the bench because they’ll never be needed again for the current fight. The stack remembers only those that could still be useful later—everything else is settled right then and there.

Wielding the Power (Code & Examples)

Problem 1: Next Greater Element I

Given two arrays nums1 and nums2, where nums1 is a subset of nums2, find for each element in nums1 the next greater element to its right in nums2. If none exists, output -1.

Brute‑force (O(n²)) – the toothpick approach:

def next_greater_brute(nums1, nums2):
    res = []
    for x in nums1:
        i = nums2.index(x)          # O(n) search
        nxt = -1
        for y in nums2[i+1:]:       # scan right
            if y > x:
                nxt = y
                break
        res.append(nxt)
    return res

Monotonic stack (O(n)) – the real deal:

def next_greater(nums1, nums2):
    # map each number in nums2 to its next greater
    nxt = {}
    stack = []                      # will hold a decreasing stack
    for num in nums2:
        while stack and num > stack[-1]:
            prev = stack.pop()
            nxt[prev] = num         # num is the next greater for prev
        stack.append(num)
    # remaining items have no greater element
    while stack:
        nxt[stack.pop()] = -1

    # build answer for nums1
    return [nxt[x] for x in nums1]

Why it works:

• The stack stays decreasing (top is smallest).
• When we see a new num that’s bigger than the top, we know `num*is* the next greater for that top element, because everything between them was ≤ the top (otherwise it would have been popped earlier).
• Each element is pushed once, popped once → O(n).

Common trap: Forgetting to clear the stack at the end. Those left‑over items truly have no greater element, so we must assign -1 to them; otherwise the map will be incomplete.

Problem 2: Largest Rectangle in Histogram

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

Brute‑force would try every left‑right pair → O(n²). Not pretty.

Monotonic stack solution (increasing stack):

python
def largest_rectangle(heights):
stack = [] # stores indices, heights are increasing
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 h < heights[stack[-1]]:
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


Why it works:

• The stack keeps indices of bars in non‑decreasing height order.
• When a lower bar appears, we know the bar at the stack’s top can’t extend further right—its right boundary is i‑1.
• The left boundary is the index now on top of the stack (after popping) because everything between that index and the popped bar is taller.
• Each index is pushed and popped once → O(n).

Typical mistake: Using <= instead of < when deciding to pop. With equal heights you’d pop prematurely and lose possible wider rectangles. Stick to strict < for the “first smaller on the right” logic.

Why This New Power Matters

Armed with a monotonic stack, you can crush a whole family of interview questions in linear time:

• Daily Temperatures (next warmer day)
• Sum of Subarray Minimums (a classic LeetCode hard)
• Trapping Rain Water (view as two monotonic passes)
• Online stock span

The pattern is always the same: find the next element that breaks a monotonic condition, and the stack gives you that answer in O(1) amortized time per element. No more nested loops, no more “I hope the test cases are small.” You walk in, you solve, you walk out feeling like you just dodged Agent Smith’s bullets and lived to tell the tale.

Your Turn

Pick one of the problems above (or find a new one that smells like “next greater/lesser”) and implement it with a monotonic stack. Try to explain to a friend why each push/pop corresponds to a real decision about the array’s structure.

When you get it working, drop a comment with your solution or a link to your repo—I’d love to see your take! Happy stacking! 🚀