Monotonic Stack: The Matrix of Array Problems

The Quest Begins (The "Why")

I still remember the first time I faced an interview question that asked for the next greater element for every item in an array. My brain went straight to the classic double‑loop solution: for each index, scan forward until you find a bigger number. It felt like grinding through a boss fight with a wooden sword — slow, frustrating, and inevitably timing out on larger test cases. I spent a good chunk of my prep time staring at those O(n²) loops, wondering if there was a hidden shortcut that the interviewers were too polite to mention.

The turning point came when a mentor tossed a single line at me: “What if you could remember what you’ve already seen, and use it to skip work?” That sounded like magic, but I was skeptical. I started sketching on a napkin, trying to see a pattern. Spoiler: the pattern was a monotonic stack, and once it clicked, the whole problem felt like a lightsaber slicing through butter.

The Revelation (The Insight)

So what’s the secret sauce? Imagine you’re walking through a hallway of lockers, each locker numbered with the array value. You want to know, for each locker, the first locker to its right that has a higher number. If you simply walk forward and peek at every locker, you’ll re‑check the same lockers over and over.

A monotonic stack flips that around: you keep a stack of indices whose values are strictly decreasing (for a “next greater” problem). As you move left‑to‑right, whenever the current value is greater than the value at the stack’s top, you’ve found the next greater element for that stacked index. You pop it, record the answer, and keep checking — because the current value might be the next greater for several previous indices, all the way back until the stack’s decreasing property holds again.

Why does this work?

• Each index is pushed onto the stack once and popped at most once.
• The total work is therefore proportional to the number of elements, giving us O(n) time.
• The stack itself stores at most n indices, so O(n) space.

It’s like having a running tally of “candidates waiting for a bigger number.” When a bigger number shows up, it resolves all the waiting candidates in one go — no need to revisit them later.

Wielding the Power (Code & Examples)

Before: The Brute‑Force Grind

function nextGreaterElement(nums) {
  const res = new Array(nums.length).fill(-1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) {
        res[i] = nums[j];
        break; // stop at the first greater
      }
    }
  }
  return res;
}

Two nested loops → O(n²). Works fine for tiny inputs, but chokes on anything beyond a few thousand elements.

After: The Monotonic Stack Spell

function nextGreaterElement(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = []; // will store indices

  for (let i = 0; i < nums.length; i++) {
    // Resolve all indices waiting for a bigger number
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop();
      res[idx] = nums[i];
    }
    stack.push(i);
  }
  // Remaining indices already have -1 (no greater to the right)
  return res;
}

Why it feels like a win:

• Each element is pushed once, popped once → linear time.
• No extra scans, no wasted comparisons.
• The code is short enough to type out in an interview without sweating.

Real‑world interview flavor: Daily Temperatures

LeetCode 739 asks: given daily temperatures, output how many days you must wait until a warmer temperature. The same monotonic stack pattern applies, just storing indices and computing distance instead of the value itself.

function dailyTemperatures(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];

  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
      const prev = stack.pop();
      answer[prev] = i - prev;
    }
    stack.push(i);
  }
  return answer;
}

Same O(n) guarantee, same satisfying “pop‑until‑you‑can’t” rhythm.

A Bonus Trap to Avoid

A common slip is to push the value instead of the index onto the stack. If you do that, you lose the ability to compute distances or update the correct position in the result array. Always store indices — they’re the keys that let you map back to the original array.

Why This New Power Matters

Walking away from that interview with a monotonic stack in your toolkit felt like unlocking a new character class in an RPG. Suddenly, problems that once seemed like grinding quests — next greater element, previous smaller element, largest rectangle in a histogram, trapping rain water — all fell under the same elegant pattern.

You can now:

• Slip into any “next/previous something” interview question with confidence.
• Write solutions that run in linear time, impressing interviewers who care about scalability.
• Spot the pattern in the wild: whenever you see a need to compare an element with something to its left or right while discarding irrelevant candidates, think monotonic stack.

It’s not just a trick; it’s a mindset shift — from “scan everything every time” to “keep only what matters, and let the current element resolve the waiting.”

Your Turn

Grab a piece of paper (or your favorite IDE) and try the Largest Rectangle in Histogram problem (LeetCode 84). Sketch the monotonic stack approach on your own before looking up the solution. When it clicks, you’ll feel that same rush I did when the O(n²) nightmare turned into a clean, linear‑time win.

What’s the next array dragon you’ll slay with your new stack‑powered sword? Drop your thoughts in the comments — I’d love to hear how it went! 🚀