The Quest Begins (The "Why")
Ever stared at a problem like “find the next greater element for every item in an array” and felt your brain start to glitch? I remember grinding through a coding interview, eyes glazing over as I tried nested loops, then a hash map, then a weird sweep‑line trick that just made things worse. The brute‑force O(n²) solution felt like trying to defeat a final boss with a wooden spoon—sure, you could swing it, but you’d be exhausted before the health bar even moved.
That frustration sparked a question: Is there a way to process the array in a single pass while still remembering enough about the past to answer “what’s next?” The answer turned out to be a deceptively simple data structure that feels like discovering a hidden cheat code: the monotonic stack.
The Revelation (The Insight)
At its core, a monotonic stack is just a stack that never lets its elements break a certain order—either always increasing or always decreasing. Why does that help? Think of the stack as a memory of “unresolved” candidates. When we walk left‑to‑right through the array, each new element can potentially be the answer for several previous elements that are waiting for a bigger (or smaller) neighbor.
If we maintain a decreasing stack (top is the smallest), then every time we see a value x that is greater than the stack’s top, we know x is the next greater element for that top element—because anything between them was smaller and therefore couldn’t satisfy the condition. We pop it, record the answer, and keep checking until the stack’s top is no longer smaller than x.
The magic is that each element is pushed once and popped at most once. No element ever gets revisited after it’s resolved, so the total work is linear. It’s like watching Neo dodge bullets in The Matrix: each bullet (array element) is dealt with exactly once, and the slow‑motion effect (the stack) lets us see the whole trajectory without rewinding.
Formally:
- Invariant: The stack stores indices in strictly decreasing order of their values (for next‑greater).
-
When we see a new value
arr[i]: whilearr[i] > arr[stack.top()], we’ve found the next greater forstack.top(). Pop and setanswer[stack.top()] = i. - After the loop, any indices left in the stack have no greater element to their right (answer = -1).
The same idea works for “previous smaller”, “next smaller”, “largest rectangle in a histogram”, etc.—just flip the comparison direction.
Wielding the Power (Code & Examples)
Example 1: Next Greater Element (LeetCode 496 – “Next Greater Element I”)
The struggle (O(n²) attempt)
function nextGreaterElement(nums1, nums2) {
const res = [];
for (let x of nums1) {
let found = false;
for (let y of nums2) {
if (y === x) found = true;
else if (found && y > x) {
res.push(y);
break;
}
}
if (!found || res.length === nums1.length) res.push(-1);
}
return res;
}
Two nested loops → O(n*m) time, painful when nums2 is large.
The victory (monotonic stack, O(n+m))
function nextGreaterElement(nums1, nums2) {
const map = new Map(); // value -> its next greater
const stack = []; // monotonic decreasing stack of values
for (const val of nums2) {
while (stack.length && val > stack[stack.length - 1]) {
const smaller = stack.pop();
map.set(smaller, val); // we just found the next greater for `smaller`
}
stack.push(val);
}
// Remaining elements have no greater to the right
for (const val of stack) map.set(val, -1);
return nums1.map(x => map.get(x));
}
Why it works: Each val pushes onto the stack once. The inner while pops every element that is smaller than val exactly when val becomes their first greater to the right. No element is examined more than twice → linear time.
Common trap: Forgetting to clear the stack after the loop. If you leave leftover indices, you’ll incorrectly assign undefined instead of -1 for those elements. Always finalize the remaining stack.
Example 2: Largest Rectangle in a Histogram (LeetCode 84)
The struggle: Brute force checks every pair of bars → O(n²).
The victory: Use an increasing stack of indices. When a bar lower than the stack’s top appears, the top bar’s right boundary is found; its left boundary is the new stack top after popping.
function largestRectangleArea(heights) {
const stack = []; // stores indices, heights increasing
let maxArea = 0;
const n = heights.length;
for (let i = 0; i <= n; i++) { // extra iteration with height 0 to flush stack
const curHeight = i === n ? 0 : heights[i];
while (stack.length && curHeight < heights[stack[stack.length - 1]]) {
const height = heights[stack.pop()];
const width = stack.length
? i - stack[stack.length - 1] - 1 // between current i and new top
: i; // popped bar extends to start
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
Why it works: The stack always holds indices of bars in non‑decreasing height order. When we encounter a lower bar, we know the rectangle limited by the popped bar cannot extend further right—its right edge is i-1. The new stack top (if any) gives the nearest smaller bar to the left, giving the maximal width. Each index is pushed and popped once → O(n).
Common trap: Using <= instead of < when deciding to pop. With <= you’d treat equal heights as a boundary too early, cutting off possible wider rectangles and under‑counting area. Strict < preserves the ability to stretch across equal‑height bars.
Why This New Power Matters
Mastering the monotonic stack turns a whole class of “nearest‑greater/smaller” problems from dreaded O(n²) nightmares into clean, O(n) victories. It’s not just a trick for interview puzzles; the pattern appears in real‑world tasks like:
- Computing stock spans (the “stock span problem”).
- Finding the number of visible people in a queue.
- Detecting collisions in particle simulations.
When you internalize the invariant—the stack holds unresolved candidates in a strict order—you stop memorizing solutions and start designing them. You’ll spot the opportunity to use a monotonic stack the same way a seasoned guitarist spots a chord progression: instantly, and with confidence.
So next time you stare at an array and feel that familiar dread, remember: you’ve got a hidden cheat code. Push, pop, let the stack do the heavy lifting, and watch the solution fall into place like Neo dodging bullets—slow, smooth, and unstoppable.
Your turn: Try applying a monotonic stack to “Daily Temperatures” (LeetCode 739) or “Maximum Width Ramp” (LeetCode 962). Share your approach in the comments—let’s see who can crack it with the fewest lines! Happy coding!
