What is the brute force approach and complexity for Next Greater Element I?

For each nums1 value, locate it in nums2 and walk right to the first bigger number with time complexity O(N · M) and space complexity O(1).

What is the optimal approach and complexity for Next Greater Element I?

One pass over nums2; a bigger arrival pops and answers every smaller waiting value with optimal time complexity O(N + M) and space complexity O(M).

How do you identify the pattern for Next Greater Element I?

Look for key signals in the prompt: "first number to the right that is bigger" indicates Next greater element → monotonic stack, decreasing.; "distinct numbers" indicates A value can be a map key, so answers can be stored by value instead of by index.; "nums1 is a subset of nums2" indicates Compute answers for all of nums2 once, then just look up the ones nums1 asks for..

Next Greater Element I

Easy·LeetCode #496Basic Anchor

LeetCode

Jump:

30-Second Mental ModelMonotonic Stack (decreasing) — next greater element

Complexity:O(N · M)→O(N + M)

Key Insight

Read nums2 once, left to right. Keep a stack of numbers that are still waiting for a bigger number. When x arrives, pop every waiting number smaller than x; x is the first bigger number each of them has met, so it is their answer. Store it in a hash map value → next greater. Then push x. Numbers left at the end get -1. Finally answer nums1 with one lookup each.

Core Validity Invariant

The stack always decreases from bottom to top. Every number on it is still waiting, and the top is the smallest waiting number, so it is the first one a bigger arrival can answer.

Problem

You get two arrays of distinct numbers, nums1 and nums2. Every number in nums1 also appears somewhere in nums2.

For a number x, its next greater element is the first number to the right of x in nums2 that is bigger than x. If there is none, the answer is -1.

For each number in nums1, return its next greater element (looked up in nums2), in the same order as nums1.

Input

Two integer arrays nums1 and nums2. All values are distinct, and nums1 is a subset of nums2.

Output

An array ans of the same length as nums1, where ans[k] is the next greater element of nums1[k] in nums2, or -1.

Example 1

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

Output: [-1, 3, -1]

In nums2, nothing to the right of 4 is bigger. The first number after 1 that is bigger is 3. 2 is the last number, so nothing is after it.

Example 2

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

Output: [3, -1]

After 2 comes 3, which is bigger. 4 is the last number.

Constraints

• 1 ≤ nums1.length ≤ nums2.length ≤ 1000
• 0 ≤ nums1[i], nums2[i] ≤ 10^4
• All values in nums1 and nums2 are distinct
• Every value of nums1 appears in nums2

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Does the answer depend on nums1 at all, or only on where the number sits in nums2?
2.
If I knew the next greater element for every value of nums2, how would I answer nums1 fast?
3.
When a big number arrives while reading nums2 left to right, which earlier numbers has it just answered?
4.
Once a number has found its next greater element, do I ever need it again?
5.
If 5 is still waiting and then 3 arrives, can 3 be the answer for 5? Can 3 still need an answer of its own?

Brute force approach

Idea

Do exactly what the statement says. For each x in nums1, find its position in nums2, then walk to the right until you see a number bigger than x. That number is the answer; if you reach the end, the answer is -1.

Thinking process

1
The definition is "the first bigger number to the right of x in nums2", so I need x's position in nums2.
2
Find it with a simple scan.
3
From there, walk right and stop at the first bigger number.
4
Each nums1 value can cost a full pass over nums2, so the total is O(n · m).

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int m = nums2.size();
        vector<int> ans;
        for (int x : nums1) {
            // 1. Find where x sits in nums2.
            int pos = 0;
            while (nums2[pos] != x) pos++;

            // 2. Walk right from there until something bigger shows up.
            int next = -1;
            for (int j = pos + 1; j < m; j++) {
                if (nums2[j] > x) {
                    next = nums2[j];
                    break;   // the FIRST bigger one is the answer
                }
            }
            ans.push_back(next);
        }
        return ans;
    }
};

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums2.length;
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int x = nums1[i];
            // 1. Find where x sits in nums2.
            int pos = 0;
            while (nums2[pos] != x) pos++;

            // 2. Walk right from there until something bigger shows up.
            int next = -1;
            for (int j = pos + 1; j < m; j++) {
                if (nums2[j] > x) {
                    next = nums2[j];
                    break;   // the FIRST bigger one is the answer
                }
            }
            ans[i] = next;
        }
        return ans;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        m = len(nums2)
        ans = []
        for x in nums1:
            # 1. Find where x sits in nums2.
            pos = 0
            while nums2[pos] != x:
                pos += 1

            # 2. Walk right from there until something bigger shows up.
            next_val = -1
            for j in range(pos + 1, m):
                if nums2[j] > x:
                    next_val = nums2[j]
                    break   # the FIRST bigger one is the answer

            ans.append(next_val)
        return ans

export function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const m = nums2.length;
    const ans: number[] = [];
    for (const x of nums1) {
        // 1. Find where x sits in nums2.
        let pos = 0;
        while (nums2[pos] !== x) pos++;

        // 2. Walk right from there until something bigger shows up.
        let next = -1;
        for (let j = pos + 1; j < m; j++) {
            if (nums2[j] > x) {
                next = nums2[j];
                break;   // the FIRST bigger one is the answer
            }
        }
        ans.push(next);
    }
    return ans;
}

Complexity

Time O(N · M)Space O(1)

N = nums1.length, M = nums2.length. With both at 1000 that is about 10^6 steps, which passes here. But the same scan for every element of a big array (the usual version of this problem) is O(M²). Only O(1) extra memory besides the output.

Optimized approach

Idea

Start from brute force

The brute force starts a fresh scan to the right for every number it is asked about.

Find the repeated work

Those scans walk over the same stretch of nums2 again and again. In [6, 5, 4, 3, 2, 1, 7], the scan for 6, for 5, for 4 … all walk to the same 7. One pass could have told all of them at once.

Define the state — what variables do I need?

st: vector<int> used as a stack: numbers of nums2 already read that have not found a bigger number yet. They decrease from bottom to top.
nextGreater: unordered_map<int,int>: value → its next greater element (or -1). Filled when the value is popped.
x: The number of nums2 being read now.

Define validity

The stack always decreases from bottom to top. Every number on it is still waiting, and the top is the smallest waiting number, so it is the first one a bigger arrival can answer.

Define the transitions — when does each pointer move, and why is it safe?

stack not empty and top < x

nextGreater[top] = x; pop

x is bigger than top, and every number between them was smaller or equal to top (otherwise top would already be answered). So x is the first bigger number to its right.

stack empty or top > x

push x

x cannot answer anyone left on the stack, and x still needs its own answer. Pushing it keeps the stack decreasing.

after nums2 is finished

every value still on the stack → -1

Nothing to their right was bigger.

What does the current window add to the answer?

Each pop writes exactly one final answer into the map. After the pass, every value of nums2 has an answer, and nums1 just reads its values from the map.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> nextGreater;   // value -> its next greater value in nums2
        vector<int> st;                        // values still waiting; they decrease bottom -> top

        for (int x : nums2) {
            // x is bigger than everything smaller on top, and it is the
            // first bigger value they have met, so x is their answer.
            while (!st.empty() && st.back() < x) {
                nextGreater[st.back()] = x;
                st.pop_back();
            }
            st.push_back(x);   // x now waits for its own next greater
        }
        // Whatever is still on the stack never met a bigger value.
        for (int v : st) nextGreater[v] = -1;

        vector<int> ans;
        for (int x : nums1) ans.push_back(nextGreater[x]);
        return ans;
    }
};

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();   // value -> its next greater value in nums2
        Deque<Integer> st = new ArrayDeque<>();                // values still waiting; they decrease bottom -> top

        for (int x : nums2) {
            // x is bigger than everything smaller on top, and it is the
            // first bigger value they have met, so x is their answer.
            while (!st.isEmpty() && st.peek() < x) {
                nextGreater.put(st.pop(), x);
            }
            st.push(x);   // x now waits for its own next greater
        }
        // Whatever is still on the stack never met a bigger value.
        for (int v : st) {
            nextGreater.put(v, -1);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = nextGreater.get(nums1[i]);
        }
        return ans;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater: Dict[int, int] = {}   # value -> its next greater value in nums2
        st: List[int] = []                  # values still waiting; they decrease bottom -> top

        for x in nums2:
            # x is bigger than everything smaller on top, and it is the
            # first bigger value they have met, so x is their answer.
            while st and st[-1] < x:
                next_greater[st.pop()] = x
            st.append(x)   # x now waits for its own next greater

        # Whatever is still on the stack never met a bigger value.
        for v in st:
            next_greater[v] = -1

        return [next_greater[x] for x in nums1]

export function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const nextGreater = new Map<number, number>();   // value -> its next greater value in nums2
    const st: number[] = [];                        // values still waiting; they decrease bottom -> top

    for (const x of nums2) {
        // x is bigger than everything smaller on top, and it is the
        // first bigger value they have met, so x is their answer.
        while (st.length > 0 && st[st.length - 1] < x) {
            nextGreater.set(st.pop()!, x);
        }
        st.push(x);   // x now waits for its own next greater
    }
    // Whatever is still on the stack never met a bigger value.
    for (const v of st) {
        nextGreater.set(v, -1);
    }

    return nums1.map((x) => nextGreater.get(x)!);
}

Complexity

Time O(N + M)Space O(M)

The while loop can pop many numbers for one x, but every number is pushed once and popped at most once, so all the pops together are at most M.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each nums1 value, locate it in nums2 and walk right to the first bigger number	O(N · M)	O(1)
Optimal	One pass over nums2; a bigger arrival pops and answers every smaller waiting value	O(N + M)	O(M)

Why does this belong to this pattern?

Clues in the problem statement

“first number to the right that is bigger”Next greater element → monotonic stack, decreasing.
“distinct numbers”A value can be a map key, so answers can be stored by value instead of by index.
“nums1 is a subset of nums2”Compute answers for all of nums2 once, then just look up the ones nums1 asks for.

For each element+first bigger value to the right+one left-to-right pass→Monotonic Stack (decreasing) — next greater element

This is the anchor of the sub-pattern: the plain "next greater" question. The only extra is the hash map, because answers are asked for by value. Daily Temperatures asks for a distance instead (so the stack holds indices), Next Greater Element II makes the array circular, and Car Fleet hides the same "who blocks me" idea behind arrival times.

Don't make this mistake

Using an increasing stack (popping while top > x)

✗ while (!st.empty() && st.back() > x) { nextGreater[st.back()] = x; st.pop_back(); }

✓ while (!st.empty() && st.back() < x) { nextGreater[st.back()] = x; st.pop_back(); }

Pattern-confusion trap. Popping when the new number is smaller finds the next smaller element, a different sub-pattern. Ask: "who does x answer?" For next greater, x answers the numbers smaller than it, so pop while top < x, which keeps the stack decreasing.

Using if instead of while

✗ if (!st.empty() && st.back() < x) { ... }

✓ while (!st.empty() && st.back() < x) { ... }

One big number can answer many waiting numbers. In [6, 5, 4, 7], 7 answers 4, 5 and 6. With if, only 4 gets its answer.

Forgetting the leftovers

✗ for (int x : nums1) ans.push_back(nextGreater[x]); // never set the leftovers

✓ for (int v : st) nextGreater[v] = -1; // before the lookups

With unordered_map, operator[] on a missing key gives 0, not -1. Numbers that never found a bigger one would wrongly return 0.

Running the stack over nums1

The next greater element is defined by positions in nums2. nums1 is in a different order, so a stack over nums1 answers the wrong question. Build the map from nums2, then use nums1 only for lookups.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Daily Temperatures