Next Greater Element: The Monotonic Stack in Its Purest Form

In the stock span problem, we met the monotonic stack for the first time — but it was wearing a business suit, dressed up as a finance question. Today we meet the same idea with its suit off, in its plainest and most honest form: the next greater element. If stock span was the story, this is the grammar underneath it.

The Problem

We are given an array of numbers. For each element, we must find its next greater element — the first number to its right that is bigger than it. If no such number exists, we write -1.

Let us take a small example:

Array:  [4,  5,  2,  25]
Answer: [5,  25, 25, -1]

Reading it out:

• 4 → looking right, the first bigger number is 5. ✅
• 5 → looking right, 2 is smaller, then 25 is bigger. Answer is 25.
• 2 → the next bigger number is 25.
• 25 → nothing to its right is bigger, so -1.

Simple to state. The interesting part, as always, is doing it fast.

The Brute-Force Idea

The obvious solution: for each element, walk to the right until you find something bigger.

function nextGreaterBrute(arr) {
    let n = arr.length;
    let result = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                result[i] = arr[j];
                break;
            }
        }
    }
    return result;
}

Correct, and perfectly readable. But it is O(n²) — for a decreasing array like [5, 4, 3, 2, 1], every element scans all the way to the end. The interviewer will smile and ask, "Can you do it in one pass?"

Yes. And the way we do it flips the whole problem around.

The Key Insight (Flip the Question)

The brute force asks, for each element, "who is my next greater element?" That forces us to look forward, again and again.

The clever move is to ask the opposite question:

When I arrive at a new element, for whom am I the answer?

Think about it. When I stand on 25, I am the "next greater element" for every earlier number that was still waiting and is smaller than me. So instead of each element hunting forward for its answer, each new element delivers the answer to everyone behind it who was waiting.

And who is "waiting"? Exactly the elements we have not yet answered — the ones smaller than everything that came after them so far. If we keep those waiting elements on a stack in decreasing order, then a new element can simply pop off everyone it is bigger than, hand each of them its answer, and take its place in the queue of the waiting.

That stack — always holding the "still unanswered, still decreasing" elements — is the monotonic stack.

The Elegant O(n) Solution

We keep a stack of indices whose next greater element has not been found yet. For each new element, we pop every waiting element it beats, and record the current element as their answer.

function nextGreaterElements(arr) {
    let n = arr.length;
    let result = new Array(n).fill(-1);
    let stack = []; // indices whose next greater element is still unknown

    for (let i = 0; i < n; i++) {
        // the current element is the "next greater" for every
        // waiting element on the stack that is smaller than it
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            let idx = stack.pop();
            result[idx] = arr[i];
        }

        // this element is now waiting for its own next greater element
        stack.push(i);
    }

    // whatever is left on the stack never found a greater element → stays -1
    return result;
}

let arr = [4, 5, 2, 25];
console.log(nextGreaterElements(arr)); // [5, 25, 25, -1]

Walking Through the Code

Let us not run away after pasting. Let us feel it.

Why store indices?

Because we need to write the answer back into result[idx] at the correct position. The index tells us where the waiting element lives; arr[idx] gives us its value when we need to compare. Storing indices is the small habit that makes almost all monotonic-stack problems cleaner.

The while loop — the heart of it:

while (stack.length > 0 
       && arr[stack[stack.length - 1]] < arr[i]) {
    let idx = stack.pop();
    result[idx] = arr[i];
}

Read this as a sentence: "As long as the element waiting on top of the stack is smaller than me, I am its answer — so give it my value and remove it from the waiting list." Each element we pop here has just found its next greater element, forever. It never comes back.

The push:

stack.push(i);

After clearing out everyone smaller, the current element joins the waiting list. Notice the stack always stays in decreasing order of value — that is the "monotonic" property, and it is maintained automatically.

What is left at the end?

Anything still sitting on the stack when the loop ends never met a bigger number to its right. Since we pre-filled result with -1, those positions are already correct. No extra work needed.

Let Us Trace It

Array [4, 5, 2, 25]. Watch the stack (showing indices) and the answers being filled:

At the end, index 3 is still on the stack, so result[3] stays -1. Final answer: [5, 25, 25, -1]. Exactly right — and notice we never once scanned forward manually.

Why Is This O(n)?

Same amortised argument as stock span, and worth repeating because interviewers love it: each index is pushed exactly once and popped at most once. The while loop looks scary nested inside the for, but across the whole run it does at most n pops in total. So the combined work is O(n), not O(n²).

• Time: O(n) — every element pushed once, popped at most once.
• Space: O(n) — in the worst case (a strictly decreasing array), everyone waits on the stack at the same time.

A Common Variation: The Circular Array

A very popular follow-up is: "What if the array is circular?" — meaning after the last element you wrap around to the front. The neat trick is to loop 2n times instead of n, using i % n to index, and only push during the first pass. Same stack, same logic, just walked around the circle once more. If you understand the version above, that twist takes only a couple of lines.

Final Thoughts

Next greater element is the skeleton of the monotonic stack. Stock span, daily temperatures, largest rectangle in a histogram, trapping rain water — strip away their stories and you will find this exact loop beating at the centre. The one idea to carry away is this:

Do not make each element search forward. Let each new element look backward and resolve everyone it beats.

Get comfortable flipping the question like that, and a whole shelf of "hard" array problems will start to feel like old friends.

Happy coding, and all the best for your interviews!