Next Greater Element I

EasyMonotonic Stack · Hash Map🧩 Monotonic Stack LeetCode #496 ↗Updated Oct 30, 2026

Problem

You get two arrays of distinct integers, where nums1 is a subset of nums2. For each value in nums1, locate it in nums2 and report the first value to its right that is larger, or -1 if none exists. Return the answers in the order of nums1.

Inputnums1 = [4,1,2], nums2 = [1,3,4,2]Output[-1,3,-1]

Inputnums1 = [2,4], nums2 = [1,2,3,4]Output[3,-1]

1 ≤ nums1.length ≤ nums2.length ≤ 1000 · all values distinct · Follow-up: O(nums1.length + nums2.length).

Try it yourself

Java

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Answer the question for every element of nums2 in one pass with a decreasing stack: when a bigger value arrives, it is the next greater element of everything it pops. Store those answers in a map and just look up nums1.

PatternMonotonic Stack

Instinct Each element needs its nearest bigger or smaller neighbour (next warmer day, span, widest bar) - keep a sorted stack of waiting indices.

Memory hack Tall people block the view - a newcomer kicks out everyone shorter waiting behind, and each kicked-out person just found their answer.

Open the Monotonic Stack guide →

Approaches

Brute ForceLocate, then Scan Right

Time O(m · n)Space O(1) extra

For each query value, walk nums2 until you find it, then keep walking until a larger value shows up. Distinct values guarantee the first match is the right position.

Java

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] ans = new int[nums1.length];
    for (int q = 0; q < nums1.length; q++) {
        int pos = 0;
        while (nums2[pos] != nums1[q]) pos++; // find the value
        ans[q] = -1;
        for (int j = pos + 1; j < nums2.length; j++) {
            if (nums2[j] > nums1[q]) {
                ans[q] = nums2[j];
                break;
            }
        }
    }
    return ans;
}

Fine for the given limits, but repeats the same scans for every query.

OptimalDecreasing Stack + Map

Time O(m + n)Space O(n)

Scan nums2 keeping a stack of values still waiting for a larger neighbour; it is decreasing from bottom to top. A new value pops every smaller waiting value and becomes their answer. Values left on the stack never find one and map to -1 by default.

Java

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> nextGreater = new HashMap<>();
    Deque<Integer> stack = new ArrayDeque<>(); // values awaiting a bigger one
    for (int x : nums2) {
        while (!stack.isEmpty() && stack.peek() < x) {
            nextGreater.put(stack.pop(), x);
        }
        stack.push(x);
    }
    int[] ans = new int[nums1.length];
    for (int q = 0; q < nums1.length; q++) {
        ans[q] = nextGreater.getOrDefault(nums1[q], -1);
    }
    return ans;
}

Dry runnums1 = [4,1,2], nums2 = [1,3,4,2]

x current changed

x=1
1
x
3

4

2

stack=[1]
x=3
1

3
x
4

2

pop 1: 1→3
x=4
1

3

4
x
2

pop 3: 3→4
x=2
1

3

4

2
x
stack=[4,2]
end
1

3

4

2

4,2 → -1 ✔

Each value is pushed and popped once — meets the follow-up.

Pro tip

Store indices instead of values if the array may contain duplicates (e.g. Next Greater Element II).

At a glance

Level	Approach	Time	Space
Brute Force	Locate, then Scan Right	`O(m · n)`	`O(1) extra`
Optimal	Decreasing Stack + Map	`O(m + n)`	`O(n)`

Common pitfalls

Searching to the right of the value in nums1 instead of its position in nums2.
Popping on ≤ vs < doesn't matter here only because values are distinct.
Forgetting that elements still on the stack at the end have answer -1.

Interview tips

Mention there is no real middle step: the jump is from repeated scans to one shared pass.
Say aloud what the stack holds: values still waiting for a larger neighbour.
Argue amortized O(n): every value is pushed once and popped at most once.

Pattern

Monotonic stack → “next greater / smaller element” for every position in one pass.

My notes saved in this browser