Monotonic Stack: The Secret Weapon from 'The Matrix' (Yes, Really)

The Quest Begins (The "Why")

Honestly, I used to dread interview questions that asked for the next greater element or the largest rectangle in a histogram. My first instinct was always to nest two loops, compare every pair, and watch the runtime blow up to O(n²) as the input size grew. I’d stare at the screen, feeling like I was stuck in a endless hallway of brute force, waiting for the interviewer to nod politely while I sweated over a timeout.

There had to be a better way—something that felt less like grinding through a grindfest and more like uncovering a hidden shortcut. That’s when I stumbled upon the monotonic stack, and honestly, it felt like discovering the cheat code in Contra: suddenly the impossible became trivial.

The Revelation (The Insight)

So what’s the magic? A monotonic stack is just a stack that keeps its elements in a strictly monotonic order—either always increasing or always decreasing—as we sweep through the array. The beauty is that each element is pushed onto the stack once and popped at most once. Because of that, the total work is linear, O(n), even though we might be looking at many elements while popping.

Why does this give us the answer? Let’s take the classic Next Greater Element problem: for each position i, we want the first element to its right that is larger than nums[i].

If we walk from left to right and maintain a decreasing stack (top is smallest), then:

• When we see a new value x, any element on the stack that is smaller than x has just found its next greater element—it’s x!
• We pop those smaller elements, record the answer for them, and keep popping until the stack’s top is ≥ x (or the stack empties).
• Then we push x onto the stack, preserving the decreasing invariant.

Because each element can only be popped when it finally meets a larger neighbor, we never do redundant work. The stack never holds more than O(n) items, and each item experiences at most one push and one pop. That’s the core insight: the stack enforces a causal relationship—once an element is blocked by a larger one, it’s settled forever.

The same idea works for previous smaller, next smaller, largest rectangle in histogram, stock span, and many more. The only change is whether we keep an increasing or decreasing stack and what we record when we pop.

Wielding the Power (Code & Examples)

Before: The Brutal O(n²) Approach (Next Greater Element)

function nextGreaterElementBrute(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;
      }
    }
  }
  return res;
}

Ugly, right? Two nested loops, and if the array is descending we scan the whole tail for every index.

After: The Monotonic Stack O(n) Solution

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

  for (let i = 0; i < nums.length; i++) {
    // Resolve all indices that see nums[i] as their next greater
    while (stack.length && nums[i] > nums[stack[top]]) {
      const idx = stack.pop();
      res[idx] = nums[i];
    }
    stack.push(i);
  }
  return res;
}

Why it works:

• The stack holds indices whose next greater hasn’t been seen yet, and they’re in decreasing order of value.
• When a new value breaks that order, it is the first greater to the right for all those smaller indices—exactly what we need.
• Each index is pushed once, popped at most once → O(n) time, O(n) space.

Another Real‑World Interview Favorite: Largest Rectangle in Histogram

Brute force (check every possible left/right boundary) → O(n²).

Monotonic stack (increasing this time) → O(n).

function largestRectangleArea(heights) {
  const stack = []; // indices with increasing heights
  let maxArea = 0;
  const extended = [...heights, 0]; // sentinel to flush the stack

  for (let i = 0; i < extended.length; i++) {
    while (stack.length && extended[i] < extended[stack[stack.length - 1]]) {
      const height = extended[stack.pop()];
      const width = stack.length
        ? i - stack[stack.length - 1] - 1
        : i; // if stack empty, rectangle extends to start
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

Common traps (the “boss level” mistakes):

• Forgetting the sentinel (0 at the end) leaves some bars unresolved.
• Mixing up whether you store indices vs. values (store indices to compute width easily).
• Not handling equal heights correctly; using < (strict) for an increasing stack ensures we pop only when a smaller appears, preserving correctness for plateaus.

Why This New Power Matters

Once you internalize the monotonic stack pattern, a whole class of “scan‑once, resolve‑later” problems becomes trivial. Think of it as gaining a new spell slot in your algorithmic grimoire:

• Stock Span – each day’s span is the distance to the previous higher price.
• Maximum Width Ramp – find max(j‑i) where A[i] ≤ A[j]; use a decreasing stack of candidates.
• Trapping Rain Water – compute left/right max boundaries with two monotonic passes.

All of these run in O(n) time and O(n) space, turning what used to feel like a nightmare into a clean, elegant sweep. The best part? The code is short enough to write on a whiteboard during an interview, and the reasoning is easy to explain: “I maintain a stack that keeps elements in monotonic order; when the order breaks, I’ve found the answer for everything I pop.”

Your Turn – Embark on Your Own Quest

Try this: given an array nums, find the maximum value of nums[j] - nums[i] such that i < j and nums[i] ≤ nums[j] (the maximum profit with one transaction, but you can only sell after you buy). Can you adapt a monotonic stack to solve it in O(n)?

Drop your solution in the comments, share aha moments, or ask if you got stuck—let’s keep the adventure going! 🚀