The Monotonic Stack: A Jedi's Guide to Slaying Array Problems

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode problem that asked for the “next greater element” for every item in an array. My naïve solution was a double loop — O(n²) — and it felt like trying to defeat a dragon with a toothpick. Every test case that passed felt like a fluke, and the larger inputs made my code sputter and die. I was stuck in a loop of frustration, wondering if there was some hidden trick I’d missed.

That’s when a friend tossed me a one‑liner: “Have you tried a monotonic stack?” I laughed — stacks are for parsing parentheses, not for hunting down next greater values! Yet curiosity got the better of me, and I dove in. What I found felt like discovering a lightsaber in a junkyard: simple, elegant, and devastatingly effective against the very problems that had been grinding me down.

The Revelation (The Insight)

So why does a monotonic stack work? Imagine you’re walking through a hallway of lockers, each labeled with a number. You want to know, for each locker, the first locker to its right that holds a higher number. If you peek at each locker and immediately shout the answer when you see a higher one, you’ll end up checking the same lockers over and over.

A monotonic stack flips that script. Instead of looking forward, we keep a decreasing stack of indices whose values we haven’t yet found a greater neighbor for. As we scan the array left‑to‑right:

• While the current element is greater than the element at the stack’s top, we’ve just found the “next greater” for that stacked index. We pop it, record the answer, and move on.
• Then we push the current index onto the stack, because it might be the next greater for some future element.

The stack stays monotonically decreasing (values go down as you go deeper), which guarantees each index is pushed once and popped once. No element lingers waiting for a comparison that will never happen. The moment we see a bigger value, we resolve all pending smaller values in one fell swoop.

That’s the magic: each element is processed a constant number of times, giving us O(n) time and O(n) auxiliary space — optimal for these “next/previous greater/smaller” flavor problems.

Wielding the Power (Code & Examples)

Let’s see the spell in action with the classic “Next Greater Element I” problem.

The Struggle (O(n²) version)

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 — fine for tiny arrays, but it chokes on anything beyond a few hundred elements.

The Victory (Monotonic Stack)

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 greater value
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop();
      res[idx] = nums[i];         // we found the next greater for idx
    }
    stack.push(i);                # current index may wait for a future greater
  }
  return res;
}

Why it’s correct:

• The stack always holds indices in decreasing order of their values.
• When nums[i] breaks that order, it is the first greater element to the right for every index we pop — because anything left in the stack is larger (or equal) and therefore cannot be answered by nums[i].
• Each index is pushed once and popped once → O(n) time.

A Second Spell: Previous Smaller Element

Sometimes you need the nearest smaller element on the left. The same pattern works; just flip the comparison.

function previousSmallerElement(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = [];

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) {
      stack.pop();               // discard elements that aren’t smaller
    }
    res[i] = stack.length ? nums[stack[stack.length - 1]] : -1;
    stack.push(i);
  }
  return res;
}

Same O(n) guarantee, just a different direction of the scan.

Why This New Power Matters

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

• Next Greater Element
• Previous Greater Element
• Next Smaller Element
• Previous Smaller Element
• Largest Rectangle in a Histogram (yes, that’s just a variation)
• Sum of Subarray Minimums

Instead of nesting loops and praying the test data is small, you now have a reliable, reusable pattern. It feels less like hacking away at a problem and more like wielding a precise tool — you know exactly what each push and pop does, and you can explain it in a sentence.

The best part? The concept transfers across languages. Whether you’re coding in Python, Java, Go, or Rust, the core idea stays identical: maintain a monotonic stack of indices and resolve pending cases as soon as a violating element appears.

Your Turn

Try this: take the “Daily Temperatures” problem (given an array of daily temperatures, output how many days you have to wait until a warmer temperature). Sketch out the monotonic‑stack solution on paper or in a scratch file, then implement it. Notice how the same push‑pop logic solves it with just a change in what you store in the result array.

If you get stuck, remember: the stack isn’t magic — it’s just a way to remember which elements are still waiting for their fate to be decided.

Go forth, conquer those array dragons, and may your stacks always stay monotonic! 🚀