Given an array of numbers, find the next greater element for every position. That is, for each element, scan to the right and find the first value that's bigger.
Take 215623. For the 2 at index 0, the answer is 5. For 1, it's also 5. For 5, it's 6. For 6? Nothing bigger exists to its right, so the answer is -1.
Simple enough to describe. But how do you actually compute it?
The brute force approach writes itself:
function nextGreater(arr: number[]): number[] { const result = 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]) { result[i] = arr[j]; break; } } } return result;}For each element, scan every element to its right. The moment you find something bigger, record it and move on. Correct? Absolutely. Fast? Not remotely.
Watch how many pairs that nested loop actually checks:
Six elements. Fifteen pair checks. Your laptop doesn't even blink.
But that nested loop is hiding something. Every element launches its own private search party, scanning rightward through everything that comes after it. The outer loop says "your turn." The inner loop says "let me check every. single. element. to your right."
That's O(n^2). Not in some abstract textbook sense — in the “your code is about to crawl” sense. Bump the input size and watch what happens to the work:
See that? At a thousand elements, you're grinding through half a million comparisons. Ten thousand? Fifty million. A hundred thousand elements — the kind of array a real coding interview might throw at you — and you're staring down five billion comparisons. Your brute force didn't just slow down. It collapsed.
And the cruel part? Almost all of that work is wasted. When element 3 scans rightward, it re-examines the exact same elements that element 2 just looked at. Every position starts from scratch, as if no one before it learned anything. The loop has amnesia.
Here's what makes it sting. When 5 shows up in [2, 1, 5, ...], it's the answer for both 2 AND 1 simultaneously. One arrival, two questions resolved — but the brute force doesn't see it. It discovers this fact twice, in two separate scans, and connects nothing.
There's a better question lurking here. Instead of each element desperately searching for its answer... what if answers announced themselves?
Here's the core idea: instead of asking “what's the next greater element for each position?”, flip it around. Ask "when a new element arrives, whose questions does it answer?"
Push elements onto a stack as you encounter them. They're waiting for an answer — waiting for something bigger to show up. When a new element arrives and it's bigger than the top of the stack, it answers that element's question. Pop the answered element, record the answer, and check the new top. Keep popping until the stack top is bigger or the stack is empty.
Watch this happen. Each element either asks a question (gets pushed) or answers questions (triggers pops). Your job: predict which elements get answered at each step.
2: scan right until you find something bigger.Did you notice what happened? The stack stays monotonically decreasing — every element on the stack is bigger than the one above it. The moment something arrives that violates this property, it triggers a cascade of pops, and each pop is a resolved question.
This is the monotonic stack pattern: a stack that maintains a strict ordering invariant. Elements aren't just stored — they're waiting. And the moment of eviction is the moment of discovery.
The beautiful thing is that each element is pushed exactly once and popped at most once. That's 2n total operations across the entire array. The algorithm is O(n):
function nextGreater(arr: number[]): number[] { const result = new Array(arr.length).fill(-1); const stack: number[] = []; // indices of unanswered elements for (let i = 0; i < arr.length; i++) { while (stack.length && arr[stack.at(-1)!] < arr[i]) { const answered = stack.pop()!; result[answered] = arr[i]; } stack.push(i); } return result;}Notice: the stack stores indices, not values. You need the index to know where to write the answer. The values are just used for comparison.
The monotonic stack pattern shows up whenever a problem asks “for each element, find the nearest element that satisfies some comparison.” The key signal is: you're looking for a relationship between pairs where one element is always to the left or right of the other.
Classic problems that use this exact pattern:
The mental model to carry forward: a monotonic stack is a collection of unanswered questions. Every push is a new question. Every pop is an answer. The element that triggers the pop is the answer.