Monotonic Stack: The Matrix of Array Problems

The Quest Begins (The "Why") I still remember the first time I faced the “Next Greater Element” interview question. The array looked innocent enough, but every brute‑force attempt felt like I was hammering a nail with a sponge— O(n²) time, nested loops, and a sinking feeling that I was missing something elegant. I spent an hour sketching out the problem on a whiteboard, muttering, “There has to be a way to look ahead without looking back every single time.” That frustration is a rite of passage for many developers. We’re taught to think in terms of scanning left‑to‑right, but some array puzzles scream for a different perspective: we need to remember what we’ve seen in a way that lets us answer questions about the future elements instantly. Enter the monotonic stack—a deceptively simple data structure that turns those scary “look‑ahead” problems into straight‑line walks. The Revelation (The Insight) So what’s the secret sauce? A monotonic stack is just a stack that maintains its elements in strictly increasing or strictly decreasing order. Why does that help? Consider the Next Greater Element problem: for each index i , we want the first element to its right that’s larger than arr[i] . If we walk from left to right and keep a stack of indices whose next greater element we haven’t found yet, the stack will naturally be decreasing in value. Why decreasing? Imagine the stack holds indices [i₁, i₂, …, i_k] where arr[i₁] > arr[i₂] > … > arr[i_k] . When we encounter a new value arr[j] , any element on the stack that is smaller than arr[j] has just found its next greater element—namely arr[j] . We pop those indices, record the answer, and stop when we hit a value that’s not smaller (or the stack empties). Then we push j onto the stack. Because each index is pushed once and popped at most once , the total work is linear: O(n) . No nested loops, no repeated scans—just a single pass with a stack that does the heavy lifting. The same invariant works for other “first bigger/smal