Monotonic Stack: The Matrix of Array Problems

The Quest Begins (The "Why")

Ever stared at an array problem and felt like you were trying to solve a Rubik’s cube blindfolded? I’ve been there. A few months ago I was prepping for a senior‑frontend interview and kept hitting the same wall: “Find the next greater element for every index” or “Calculate the largest rectangle in a histogram.” The naive solutions were O(n²) — nested loops that made my laptop whine and my brain fog. I remember spending three hours on a single LeetCode problem, only to watch my brute‑force solution time out on the biggest test case. I felt like a hero stuck in a tutorial level, knowing there had to be a secret move I was missing.

That frustration sparked a quest: Is there a way to process an array in a single pass while still remembering useful information about the elements we’ve already seen? The answer, as it turned out, lives in a deceptively simple data structure called the monotonic stack.

The Revelation (The Insight)

Here’s the magic: a monotonic stack keeps its elements strictly increasing (or decreasing) from bottom to top. Why does that help? Because when you encounter a new element, you can instantly know which previous elements it “dominates” or is “dominated by,” and you can resolve those relationships right then and there.

Think of it like this: you’re walking down a hallway of lockers (the array). Each locker has a number on it. You carry a stack of lockers you’ve seen so far, but you only keep those that are still waiting for a bigger number to appear. When you see a new locker with a higher number, you know it’s the “next greater” for every locker you pop off the stack — because those lockers were waiting for something bigger, and you just found it. After you pop them, you push the current locker onto the stack, because it might be the next greater for someone further down the hallway.

The key insight is amortized O(1) work per element. Each element is pushed onto the stack exactly once and popped at most once. No matter how the numbers dance, the total number of stack operations is bounded by 2 × n, giving us O(n) time and O(n) auxiliary space. No nested loops, no repeated scans — just a single forward pass with a cleverly maintained stack.

Wielding the Power (Code & Examples)

Problem 1: Next Greater Element

Prompt: Given an array nums, return an array result where result[i] is the next greater element to the right of nums[i]. If none exists, put -1.

The Struggle (O(n²) attempt)

function nextGreaterBrute(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;
}

Two nested loops → O(n²). I watched my CPU fan spin up on the biggest test case and felt the familiar sting of inefficiency.

The Victory (Monotonic Stack)

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

  for (let i = 0; i < nums.length; i++) {
    // While current value beats the value at the 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 as default.
  return res;
}

// Helper to read the last element without mutating the stack
Array.prototype.top = function () {
  return this[this.length - 1];
};

Why it works:

• The stack holds indices of a decreasing sequence of values.
• When nums[i] is larger than the value at the top, it is the next greater for all those smaller values, so we pop them and fill their answer.
• Each index is pushed once and popped at most once → linear time.

Common Trap

If you forget to store indices instead of values, you lose the ability to write results back to the correct position when duplicates appear. Always push indices; the value lookup is nums[stack[idx]].

Problem 2: Largest Rectangle in a Histogram

Prompt: Given an array heights representing bar heights, find the area of the largest rectangle that can be formed within the histogram.

The Struggle (Divide‑and‑Conquer or brute force)

A naive solution checks every possible left/right pair → O(n²). A recursive divide‑and‑conquer approach can degrade to O(n²) in the worst case (e.g., strictly increasing heights). I spent an afternoon trying to optimize a segment‑tree solution, only to realize I was over‑engineering.

The Victory (Monotonic Stack)

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

  for (let i = 0; i < extended.length; i++) {
    // While current height is lower than the height at stack top,
    // we have found the right boundary for the bar at stack.top().
    while (stack.length && extended[i] < extended[stack[stack.length - 1]]) {
      const height = extended[stack.pop()];
      // Width is i if stack empty (means height extends to start),
      // otherwise distance between current index and new top - 1.
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

Why it works:

• The stack maintains indices of non‑decreasing heights.
• When we encounter a lower height, we know the current bar is the first bar to the right that is lower than the bar at the stack’s top → thus the right boundary for that bar is i‑1.
• The left boundary is the index now on top of the stack after popping (or -1 if the stack is empty).
• Area = height × width. Each bar is pushed and popped once → O(n).

Common Trap

Neglecting the sentinel 0 at the end leaves bars lingering in the stack, causing you to miss rectangles that extend to the histogram’s edge. Always add a sentinel (or handle the remaining stack after the loop).

Why This New Power Matters

Mastering the monotonic stack feels like unlocking a cheat code for a whole class of array‑twiddling puzzles. Suddenly, problems that once required nested loops, recursion, or fancy data structures collapse into a clean, single‑pass solution. You’ll start spotting the pattern everywhere: “next/previous greater/smaller,” “largest subarray with constraint,” “trapping water,” “stock span,” and more.

The beauty isn’t just speed — it’s clarity. The algorithm reads like a story: you walk through the array, keep a waiting line of elements, and resolve their fates as soon as you meet their match. It’s intuitive once you see the invariants, and it’s satisfyingly efficient.

Now you have a tool that turns O(n²) frustration into O(n) triumph. Use it, share it, and watch your interview confidence (and your code’s performance) soar.

Your Turn

Grab your favorite coding challenge site and try the “Daily Temperatures” problem (LeetCode 739) using a monotonic stack. When you nail it, notice how the same pattern appears in the “Maximum Width Ramp” or “Sum of Subarray Minimums” challenges.

What’s the first array problem you’ll conquer with your new stack‑powered sword? Drop your solution or a question in the comments — I’d love to hear how it went!

---

P.S. If you ever feel stuck, remember: even Neo had to learn to see the code. Keep pushing, and the patterns will reveal themselves. 🚀