Monotonic Stack: The Matrix Approach to Tricky Array Problems

The Quest Begins (The "Why")

Ever stared at an interview question like “find the next greater element for each item in the array” and felt your brain short‑circuit? I remember the first time I saw that problem on a whiteboard. My mind went straight to nested loops, O(n²) nightmares, and the sinking feeling that I was about to get stuck in a boss fight with no health packs.

That’s when I realized I was approaching the problem like a rookie trying to slash through a horde with a butter knife. There had to be a smarter way—something that let me glide through the array once, keeping track of what mattered, and spit out the answer in linear time. Enter the monotonic stack, the unsung hero that feels like discovering a hidden cheat code in a classic game.

The Revelation (The Insight)

So what’s the secret sauce? A monotonic stack is simply a stack that maintains its elements in strictly increasing (or decreasing) order. As we sweep through the array from left to right, we push each element’s index onto the stack. Before we push, we pop off any indices whose corresponding values break the monotonic property.

Why does this work? Think of each stack entry as a “candidate” waiting for its future counterpart. When we encounter a new value that is larger (for a next‑greater‑element query) than the value at the top of the stack, we now know that this new value is the first greater element to the right for all those popped indices. Because we only pop when we’ve found a definitive answer, each index is pushed and popped at most once—giving us O(n) total work.

It’s like watching a line of people waiting for a ride: as soon as someone taller shows up, everyone shorter in front of them knows they’ve found their match and can step out of the line. No one gets left wondering, and nobody gets checked twice.

Wielding the Power (Code & Examples)

Problem 1: Next Greater Element

The struggle (naïve O(n²))

function nextGreaterElementNaive(arr) {
  const res = new Array(arr.length).fill(-1);
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] > arr[i]) {
        res[i] = arr[j];
        break;
      }
    }
  }
  return res;
}

That double loop is the equivalent of grinding through every enemy in a level—slow and tedious.

The victory (monotonic stack, O(n))

function nextGreaterElement(arr) {
  const res = new Array(arr.length).fill(-1);
  const stack = []; // stores indices, values are decreasing

  for (let i = 0; i < arr.length; i++) {
    // Resolve all previous indices that this element beats
    while (stack.length && arr[i] > arr[stack.top()]) {
      const idx = stack.pop();
      res[idx] = arr[i];
    }
    stack.push(i);
  }
  return res;
}

// Helper to read the top without popping (just for clarity)
Object.defineProperty(Array.prototype, 'top', {
  get() { return this[this.length - 1]; },
  configurable: true
});

Why it’s elegant

• Each index goes onto the stack once.
• Each index is removed at most once when we find its next greater.
• No nested loops, no wasted comparisons.

Problem 2: Largest Rectangle in Histogram

This one feels like trying to find the biggest platform in a side‑scroller—except the platforms have varying heights.

Naïve approach – for each bar, expand left and right until you hit a shorter bar. O(n²) again.

Monotonic stack solution – we keep indices of bars in increasing height order. When we see a bar lower than the stack’s top, we know the rectangle with the height of the stacked bar can’t extend further; we compute its area using the current index as the right boundary and the new top of the stack (after popping) as the left boundary.

function largestRectangleArea(heights) {
  let maxArea = 0;
  const stack = []; // stores indices, heights are increasing

  for (let i = 0; i <= heights.length; i++) {
    // Use a sentinel height of 0 at the end to flush the stack
    const curHeight = i === heights.length ? 0 : heights[i];

    while (stack.length && curHeight < heights[stack.top()]) {
      const height = heights[stack.pop()];
      const width = stack.length
        ? i - stack.top() - 1   // distance between current index and new top
        : i;                    // if stack empty, rectangle stretches to start
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

Again, each bar is pushed and popped once → O(n) time, O(n) space.

Common Traps to Avoid

1. Forgetting the sentinel – Without a final zero (or a sufficiently low value) you’ll leave elements stuck in the stack, missing their final area calculations.
2. Mixing up strict vs. non‑strict monotonicity – For “next greater element” we need a strictly decreasing stack (pop while current > stack.top). Using >= would incorrectly treat equal values as greater, breaking correctness for duplicate numbers.
3. Mis‑computing width – The width isn’t just i - idx; you need to account for the element now on top of the stack after popping, which marks the left boundary where the height is still valid.

Why This New Power Matters

Mastering the monotonic stack is like unlocking a universal tool in your algorithmic arsenal. Suddenly, problems that looked like they needed quadratic time—next greater/smaller element, daily temperatures, trap rain water, largest rectangle in histogram—collapse to linear time with a clean, intuitive implementation.

You’ll walk into interviews feeling less like you’re scrambling for a solution and more like you’re casting a spell you’ve practiced a hundred times. And beyond interviews, this pattern shows up in real‑world systems: streaming analytics, financial tick processing, even UI layout engines that need to know the next larger element in a sequence.

So next time you see an array and feel that familiar dread, remember: you’ve got a monotonic stack ready to turn that O(n²) nightmare into an O(n) triumph.

Your Turn

Grab a favorite array problem—maybe “daily temperatures” or “maximum width ramp”—and try solving it with a monotonic stack. Notice how the stack guides you, how each push and pop has a clear meaning, and how the solution just flows.

When you crack it, drop a comment or tweet your solution. Let’s keep pushing the limits of what we can do with a simple stack and a lot of curiosity. Happy coding!