Next Greater Element I

easyStack33 stepsJava · Python · C++

For each value in nums1, find the first larger value to its right in nums2. Scan nums2 with a decreasing stack: when a bigger value arrives, it's the next greater element for everything smaller it pops. Store answers in a map, then look up nums1.

▶ Watch the animated trace

Traced input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2] → [-1, 3, -1]. Original problem: neetcode.io/problems/next-greater-element-i

Complexity

BestO(n + m)

AverageO(n + m)

WorstO(n + m)

SpaceO(m)

Each element of nums2 is pushed and popped at most once.

Key idea

Keep the stack decreasing from bottom to top.
A new value pops every smaller value; for each, the new value is its next greater.
Whatever stays on the stack has no greater element: answer -1.
A map from value to answer handles nums1 lookups in O(1).

Common mistakes

Nested loops are O(n·m).
Values are distinct here; with duplicates you'd store indices, not values.

Solution

Java

int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> next = new HashMap<>();
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < nums2.length; i++) {
        int x = nums2[i];
        while (!stack.isEmpty() && stack.peek() < x) {
            next.put(stack.pop(), x);
        }
        stack.push(x);
    }
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) res[i] = next.getOrDefault(nums1[i], -1);
    return res;
}

Python

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    nxt = {}
    stack = []
    for x in nums2:
        while stack and stack[-1] < x:
            nxt[stack.pop()] = x
        stack.append(x)
    return [nxt.get(x, -1) for x in nums1]

C++

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> next;
    stack<int> st;
    for (int x : nums2) {
        while (!st.empty() && st.top() < x) {
            next[st.top()] = x;
            st.pop();
        }
        st.push(x);
    }
    vector<int> res;
    for (int x : nums1) res.push_back(next.count(x) ? next[x] : -1);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All decreasing Nothing is ever popped.	`nums1 = [3, 1], nums2 = [3, 2, 1]`	`[-1, -1]`
All increasing Each value is popped by the next one.	`nums1 = [1, 2], nums2 = [1, 2, 3]`	`[2, 3]`
Single element Nothing to its right.	`nums1 = [5], nums2 = [5]`	`[-1]`
Answer is far away 2 waits on the stack until 9 arrives.	`nums1 = [2], nums2 = [2, 1, 0, 0, 9]`	`[9]`