Monotonic Stack: The Fellowship of the Array

The Quest Begins (The “Why”)

I still remember the first time I stared at the Daily Temperatures problem on LeetCode, heart pounding like I was about to face a final boss. My first attempt was a double‑loop: for each day I scanned forward until I found a warmer temperature. It worked on the tiny examples, but the moment the test suite hit a 10⁵‑sized array, my solution sputtered out with a timeout. I felt like a hobbit wandering into Mordor without a map—lost, frustrated, and convinced there had to be a smarter way.

That frustration sparked a question: Is there a pattern that lets us look ahead without re‑scanning the same elements over and over? The answer turned out to be a humble data structure we often overlook—the monotonic stack.

The Revelation (The Insight)

A monotonic stack is simply a stack that stays strictly increasing (or decreasing) as we push elements. The magic lies in how we maintain that order: whenever the current element breaks the monotonicity, we pop elements that violate it. Each pop gives us a piece of information about the relationship between the popped element and the current one—usually the next greater (or next smaller) element.

Why does this give us an O(n) solution? Think of the stack as a conveyor belt. Every element gets pushed once and, if it ever gets popped, it’s popped once as well. No element is touched more than a constant number of times, so the total work is totally eliminates the nested loops that plagued my first attempt.

The intuition is easier to grasp with a story: imagine a line of people waiting for a roller coaster, sorted by height from shortest at the front to tallest at the back. When a new person arrives, we let anyone shorter than them step forward because they’ll never block the view for the newcomer. Those who step forward are exactly the elements we pop, and we can record that the newcomer is the next taller person for each of them. The line never gets chaotic; it stays monotonic, and we’ve processed everyone in a single pass.

Wielding the Power (Code & Examples)

Before: The Brutal Force

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

Ouch. Two nested loops → O(n²) time, O(1) extra space. It works, but it’s a scalability nightmare.

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):
        # Resolve all previous days that are colder than today
        while stack and t > temps[stack[-1]]:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)

    return answer

What changed?

• The stack holds indices of days whose next warmer temperature we haven’t found yet.
• As we scan left‑to‑right, whenever the current temperature t is hotter than the temperature at the stack’s top, we know we’ve found the answer for that earlier day.
• Each index is pushed once and popped at most once → O(n) time, O(n) worst‑case space (the stack itself).

Common trap: Forgetting to store indices instead of the values themselves. If you store only the temperatures you lose the distance i - prev, which is what the problem asks for.

A Second Quest: Trapping Rain Water

The same pattern appears in the classic “Trapping Rain Water” problem. Here we need to know, for each bar, the tallest bar to its left and to its right. A two‑pass monotonic‑stack solution does the job in linear time:

def trap(height):
    n = len(height)
    if n < 3:
        return 0
    water = 0
    stack = []          # stores indices of bars in decreasing height order

    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:          # no left boundary
                break
            distance = i - stack[-1] - 1
            bounded_h = min(height[stack[-1]], h) - height[bottom]
            water += distance * bounded_h
        stack.append(i)

    return water

Again, each bar is pushed and popped at most once, giving us O(n) time. The insight? The stack keeps a monotonic decreasing profile of the terrain; when we see a rise, we’ve just closed a “valley” and can compute the water trapped inside it.

Why This New Power Matters

Walking away from those interview questions with a monotonic‑stack toolkit feels like discovering a secret shortcut through a dungeon. Suddenly, problems that once seemed to need quadratic scans—next greater element, previous smaller element, stock span, sum of subarray minimums, maximum width ramp—collapse to clean linear solutions.

The pattern is universal: whenever you need to know “the next/previous element that satisfies a certain comparison”, ask yourself if a monotonic stack can maintain the relevant candidates. If the answer is yes, you’ll likely shave off a factor of n and impress your interviewer (and yourself) with both speed and elegance.

I’ve seen candidates go from “I’m stuck” to “I shipped it in five minutes” just by recognizing this pattern. It’s a confidence booster that pays off far beyond the interview—real‑world tasks like processing streaming data, implementing UI undo stacks, or even optimizing certain graph algorithms benefit from the same principle.

Your Turn

Ready to test your newfound skill? Try solving “Sum of Subarray Minimums” (LeetCode 907) using a monotonic stack. Or, if you’re feeling adventurous, tackle “Maximum Width Ramp” (LeetCode 962) and see how the stack helps you find the farthest pair where i < j and nums[i] <= nums[j].

Drop your solution or any questions in the comments—I love hearing how the fellowship of the array is treating you on your own quest. Happy coding! 🚀