Data Structures & Algorithms · Stacks and Queues

Next Greater Element I: The Monotonic Stack Pattern, Explained Once and For All

Q: What is a monotonic stack?

A monotonic stack is a regular stack with one enforced invariant: its values stay sorted (here, decreasing from bottom to top) at all times, maintained by popping any elements that would violate it before each push. The payoff is that the top always answers a "nearest greater" or "nearest smaller" question in O(1), and because each element is pushed and popped at most once, maintaining the invariant costs only O(n) across the whole array.

Q: What is the time complexity of Next Greater Element I?

O(n + m), where n is the length of nums2 and m is the length of nums1. The right-to-left scan is amortized O(n) — every element is pushed exactly once and popped at most once, so the inner while-loop's total work is bounded by n. The query phase is m hash-map lookups at O(1) each. Space is O(n) for the stack and map; the brute-force alternative is O(m·n) time.

Q: Why does the solution scan nums2 right to left?

Because "next greater" asks about what lies to the right, scanning right to left means the stack already contains every candidate that could answer the current element. At index i, the stack holds a decreasing tower of values from indices greater than i — either the top immediately answers you, or you pop dominated values until one does. A left-to-right variant exists too (it records answers at pop time instead of visit time); both are O(n), they just do their bookkeeping at different moments.

Q: Why can the hash map use values as keys instead of indices?

Because the problem guarantees all values in nums2 are distinct, each value identifies exactly one position and one next-greater answer. That's what lets nums1 queries — which are values, not indices — resolve with a single map lookup. If nums2 allowed duplicates, one value could have multiple conflicting answers; you'd switch to an index-keyed answer array instead.

Q: What happens when an element empties the stack?

It means that element is larger than every value to its right, so no next greater element exists and it maps to -1. In the code, the while-loop drains all smaller candidates, the stack.length === 0 check catches the empty case, and ngeMap[arr[i]] = -1 records it. The element then pushes itself onto the empty stack, becoming the sole candidate for everything to its left.

Solve Next Greater Element I with a monotonic stack and hash map: right-to-left scan, O(n+m) time, worked walkthrough, JavaScript code, and common mistakes.

July 12, 20268 min readBy Bhavesh Singh

monotonic stackhash mapstacksleetcode easymonotonic stack mapping

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the Next Greater Element I visualizer

Next Greater Element I looks like a lookup exercise and hides one of the highest-leverage tools in interview prep: the monotonic stack. The problem asks, for each queried value, "what's the first bigger thing to its right?" — and the naive answer rescans the array for every single query.

The stack-based answer precomputes the next greater element for every value in one linear pass, stores the results in a hash map, and answers each query in O(1). That two-phase shape — build a mapping once, query it cheaply forever — is the Monotonic Stack Mapping pattern, and it's the skeleton behind Daily Temperatures, Next Greater Element II, and Largest Rectangle in Histogram.

The problem

You're given two arrays. nums1 is a subset of nums2, and all values in nums2 are distinct. For each element x in nums1, find x inside nums2 and return the first element to its right that is strictly greater than x — or -1 if none exists.

text

Input:  nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]

// 4 sits at nums2[2]; nothing to its right (only 2) is greater → -1
// 1 sits at nums2[0]; the first greater element to its right is 3
// 2 sits at nums2[3]; nothing is to its right at all → -1

Two constraints quietly shape the optimal solution:

All values in nums2 are distinct. That means a value uniquely identifies a position, so you can key a hash map by value instead of index.
nums1 is a subset of nums2. Every query is guaranteed to exist in the map you build.

The brute force baseline

The direct translation: for each query, find it in nums2, then scan right until something bigger appears.

javascript

function nextGreaterElement(nums1, nums2) {
  return nums1.map((x) => {
    const start = nums2.indexOf(x);          // O(n) find
    for (let j = start + 1; j < nums2.length; j++) {
      if (nums2[j] > x) return nums2[j];     // O(n) scan
    }
    return -1;
  });
}

With m queries against an n-element array, that's O(m·n). The waste is obvious once you name it: every query re-walks a suffix of nums2 that previous queries already walked. If nums2 is [6, 5, 4, 3, 2, 1, 7], every query marches all the way to the 7 — the same discovery, made m times. Anything computed repeatedly for the same array should be computed once.

The key insight: precompute answers with a decreasing stack

Flip the workload. Instead of answering queries lazily, answer them all upfront: build ngeMap, a hash map from every nums2 value to its next greater element. Each nums1 query then becomes a single O(1) lookup.

The clever part is building that map in one pass. Scan nums2 from right to left, carrying a stack of "candidate" values — elements to the right of the current position that could still be someone's next greater element. The stack stays decreasing from bottom to top, which gives two properties when you arrive at arr[i]:

If arr[i] is smaller than the top, the top is its next greater element — it's the nearest candidate to the right, and it's bigger. Answer found in O(1), no popping.
If arr[i] is greater than or equal to the top, the top can never be anyone's answer again: any earlier index looking rightward hits arr[i] first, and arr[i] dominates it. Pop it — permanently — and keep popping until a survivor bigger than arr[i] appears (that's the answer) or the stack empties (the answer is -1).

Either way, arr[i] then pushes itself onto the stack, because it might be the next greater element for something further left. Every element is pushed exactly once and popped at most once, so the whole scan is amortized O(n) despite the while-loop inside the for-loop.

The optimal solution

This is the exact algorithm the visualizer steps through, with the same variable names. The parameter arr is nums2:

javascript

var nextGreaterElement = function(nums1, arr) {
    let ngeMap = {};
    let stack = [];
    let n = arr.length;

    stack.push(arr[n-1]);
    ngeMap[arr[n-1]] = -1;
    for(let i=n-2; i>=0; i--){
        let top = stack[stack.length-1];
        if(arr[i] < top){
            ngeMap[arr[i]] = top;
        }
        else {
            while(stack.length) {
                if(stack[stack.length-1] < arr[i]){
                    stack.pop();
                } else {
                    ngeMap[arr[i]] = stack[stack.length-1];
                    break;
                }
            }
            if(stack.length === 0){
                ngeMap[arr[i]] = -1;
            }
        }
        stack.push(arr[i]);
    }
    let ans = [];
    for(let i=0; i < nums1.length; i++){
        ans.push(ngeMap[nums1[i]]);
    }
    return ans;
};

The seeding step matters: the last element arr[n-1] has nothing to its right, so it maps to -1 by definition and enters the stack as the first candidate. From there the loop runs n-2 down to 0 — the fast path (arr[i] < top) resolves without touching the stack; the slow path drains dominated candidates first. After the scan, the second loop is pure lookups: a million nums1 queries wouldn't change the preprocessing cost.

Walkthrough: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Scanning arr = [1, 3, 4, 2] right to left:

Step	i	arr[i]	Comparison	Stack after (bottom → top)	ngeMap after
Seed	3	2	last element → -1 by definition	[2]	{2: -1}
1	2	4	4 ≥ top 2 → pop 2; stack empty → -1	[4]	{2: -1, 4: -1}
2	1	3	3 < top 4 → answer is 4, no pops	[4, 3]	{2: -1, 4: -1, 3: 4}
3	0	1	1 < top 3 → answer is 3, no pops	[4, 3, 1]	{2: -1, 4: -1, 3: 4, 1: 3}

Step 1 shows the popping rule earning its keep: once 4 arrives, the 2 below it can never be a next greater element for indices 0 or 1 — they'd hit 4 first — so 2 leaves the stack forever. Steps 2 and 3 show the payoff: with the stack decreasing, a smaller incoming value resolves instantly against the top.

Answer phase: nums1 = [4, 1, 2] → [ngeMap[4], ngeMap[1], ngeMap[2]] → [-1, 3, -1]. Three queries, three lookups, zero rescanning.

Complexity

Approach	Time	Space	Why
Brute force	O(m·n)	O(1)	each of m queries re-finds and re-scans nums2
Monotonic stack + map	O(n + m)	O(n)	each nums2 value pushed once, popped at most once; each query is one lookup

Don't let the nested while fool you into calling it O(n²). Charge each pop to the element being popped: an element can only be popped once in its lifetime, so total pops across the entire scan are at most n. Space is the stack plus the map, both bounded by n.

Common mistakes

Answering queries by scanning. If your solution contains indexOf inside a loop over nums1, you've written the O(m·n) baseline. The whole point is separating preprocessing from querying.
Keying the map by index instead of value. nums1 gives you values, not positions. The value-keyed map only works because nums2 values are distinct — say that out loud in an interview; it shows you read the constraints.
Forgetting the -1 cases. Two places produce -1: the seeded last element, and any element that drains the stack completely. Miss the drain case and inputs like [4, 3] | [4, 3, 2, 1] return undefineds.
Misjudging the pop condition's strictness. The code pops while top < arr[i]. With distinct values < vs <= can't differ, but in duplicate-friendly cousins of this problem strictness decides whether equal values shadow each other — derive it, don't memorize it.
Mixing the two scan directions. A left-to-right variant exists that records answers while popping instead of while visiting. Both work; a hybrid does not.
Forgetting to push arr[i] after resolving. Every element must enter the stack — even ones that resolved to -1 — because each is a potential answer for indices further left.

Where this pattern shows up next

Monotonic Stack Mapping is the gateway to a family of "nearest greater/smaller" problems:

Daily Temperatures — the same decreasing stack, but tracking indices to answer "how many days until warmer?"
Next Greater Element II — the circular version: one virtual double-pass, same stack discipline.
Evaluate Reverse Polish Notation — a different stack job (operand evaluation) that shows how versatile the structure is.
Remove Outermost Parentheses — stack thinking reduced to a single depth counter.

The fastest way to internalize the popping rule is to watch it: step through Next Greater Element I interactively and see dominated candidates flash out of the stack as each new value arrives.

FAQ

What is a monotonic stack?

A monotonic stack is a regular stack with one enforced invariant: its values stay sorted (here, decreasing from bottom to top) at all times, maintained by popping any elements that would violate it before each push. The payoff is that the top always answers a "nearest greater" or "nearest smaller" question in O(1), and because each element is pushed and popped at most once, maintaining the invariant costs only O(n) across the whole array.

What is the time complexity of Next Greater Element I?

O(n + m), where n is the length of nums2 and m is the length of nums1. The right-to-left scan is amortized O(n) — every element is pushed exactly once and popped at most once, so the inner while-loop's total work is bounded by n. The query phase is m hash-map lookups at O(1) each. Space is O(n) for the stack and map; the brute-force alternative is O(m·n) time.

Why does the solution scan nums2 right to left?

Because "next greater" asks about what lies to the right, scanning right to left means the stack already contains every candidate that could answer the current element. At index i, the stack holds a decreasing tower of values from indices greater than i — either the top immediately answers you, or you pop dominated values until one does. A left-to-right variant exists too (it records answers at pop time instead of visit time); both are O(n), they just do their bookkeeping at different moments.

Why can the hash map use values as keys instead of indices?

Because the problem guarantees all values in nums2 are distinct, each value identifies exactly one position and one next-greater answer. That's what lets nums1 queries — which are values, not indices — resolve with a single map lookup. If nums2 allowed duplicates, one value could have multiple conflicting answers; you'd switch to an index-keyed answer array instead.

What happens when an element empties the stack?

It means that element is larger than every value to its right, so no next greater element exists and it maps to -1. In the code, the while-loop drains all smaller candidates, the stack.length === 0 check catches the empty case, and ngeMap[arr[i]] = -1 records it. The element then pushes itself onto the empty stack, becoming the sole candidate for everything to its left.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the Next Greater Element I visualizer

The problem#

The brute force baseline#

The key insight: precompute answers with a decreasing stack#

The optimal solution#

Walkthrough: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

What is a monotonic stack?#

What is the time complexity of Next Greater Element I?#

Why does the solution scan nums2 right to left?#

Why can the hash map use values as keys instead of indices?#

What happens when an element empties the stack?#

Related articles