Monotonic Stack: The Matrix of Array Problems

The Quest Begins (The "Why")

I still remember the first time I stared at a coding 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 worked… on tiny test cases. But as soon as the input grew to 10⁵ elements, my solution started feeling like I was trying to defeat a final boss with a wooden spoon. The timer ticked, my confidence dropped, and I kept thinking there had to be a smarter way—something that felt less like grinding and more like unlocking a hidden cheat code.

That’s when I stumbled upon the monotonic stack. At first it looked like just another data‑structure trick, but once I understood why it works, it felt like I’d finally found the One Ring in a pile of pebbles—simple, powerful, and suddenly everything clicked.

The Revelation (The Insight)

What is a monotonic stack?

A stack that keeps its elements either strictly increasing or strictly decreasing from bottom to top. While we iterate through the array, we push the current index onto the stack only after we’ve removed (popped) any elements that would break that order.

Why does that give us O(n) time?

Think of each element as a traveler entering a hallway. The hallway (the stack) only lets travelers through if they’re taller than the one standing at the front (for a decreasing stack) or shorter (for an increasing stack). Whenever a new traveler arrives that is taller than the person at the front, that front person can never be the “next greater” for anyone behind them—because the new traveler blocks the view and is closer. So we can safely pop that front person, record the answer for it, and never consider it again.

Each index is pushed once and popped at most once. No element ever gets examined more than a constant number of times. Hence the total work is linear, O(n), with O(n) extra space for the stack (or O(1) if we reuse the input array for output).

The beauty is that the stack encodes the relationship we care about—who is waiting for a bigger/smaller neighbor—so we never need to restart a scan from scratch. It’s like having a running leaderboard that updates itself as new scores come in.

Wielding the Power (Code & Examples)

Let’s see the theory in action with two interview‑favorite problems.

Problem 1: Next Greater Element I (LeetCode 496)

Brute force (O(n²)) – the “wooden spoon” approach:

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

Monotonic stack (O(n)) – the “cheat code”:

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

  for (let i = 0; i < nums.length; i++) {
    // While current value beats the value at stack's top,
    // we have found the next greater for that index.
    while (stack.length && nums[i] > nums[stack.top()]) {
      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 works:

The stack always holds indices whose next greater element hasn’t been seen yet, and they are in decreasing order of their values. When a larger value appears, it is the first larger value to the right for every index we pop—exactly what we need. Each index is pushed once, popped once → O(n).

Common trap:

If you forget to pop equal elements when you need a strictly greater answer, you’ll incorrectly assign the next greater for duplicates. Adjust the comparison (> vs >=) based on the problem’s definition.

Problem 2: Largest Rectangle in Histogram (LeetCode 84)

Brute force (O(n²)) – try every bar as the limiting height and expand left/right until you hit a shorter bar.

Monotonic stack (O(n)) – we keep indices of bars in increasing order of height. When we encounter a bar lower than the stack’s top, we know the top bar’s right boundary is the current index; its left boundary is the new top after popping.

function largestRectangleArea(heights) {
  // Append a sentinel zero to flush remaining bars at the end
  const extended = [...heights, 0];
  const stack = []; // stores indices, monotonic increasing heights
  let maxArea = 0;

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

Why it works:

The stack guarantees that for any popped bar, the current index is the first bar to the right that is shorter, and the new stack top (if any) is the first bar to the left that is shorter. Thus the popped bar is the limiting height for the widest rectangle where it is the shortest side. Each bar is pushed and popped once → O(n).

Common trap:

Neglecting the sentinel (the extra 0 at the end) leaves bars lingering in the stack, causing you to miss rectangles that reach the histogram’s end. Adding the sentinel guarantees a final cleanup pass.

Why This New Power Matters

Mastering the monotonic stack turns a whole class of “scan‑until‑you‑find‑something” problems from O(n²) nightmares into O(n) victories. It’s not just a trick for interview puzzles; the same pattern appears in real‑world tasks like:

• Finding spill levels in terrain data (trapping rain water).
• Computing span of stock prices (stock‑span problem).
• Parsing nested structures where you need to know the nearest larger/smaller token.

When you internalize the why—that the stack maintains a invariant that lets you discard useless work permanently—you start spotting opportunities to apply it everywhere. It’s like gaining a new spell slot in your developer’s grimoire: suddenly, you can cast solutions that used to require expensive loops with a flick of the wrist.

Your Turn

Here’s a quick challenge to test your newfound ability:

Daily Temperatures (LeetCode 739) – Given an array of daily temperatures, return how many days you must wait until a warmer temperature. If there is no future day with a higher temperature, put 0.

Try solving it with a monotonic decreasing stack. Once you have it, compare your solution to the naive O(n²) approach and feel the speed difference.

If you get stuck, remember: the stack is just waiting for the next temperature that “breaks” the current monotonic trend. Pop, record the distance, push, and move on.

Go ahead—give it a try, and when it clicks, you’ll feel like you’ve just dodged a barrage of arrows in a boss fight and landed the final blow. Happy coding! 🚀