#496 Next Greater Element I

frequently reported atBloomberg Amazon Microsoft Google

the problem

In plain words

nums1 is a subset of nums2 (all values distinct). For each x in nums1, find the first number to the right of x in nums2 that is greater than x, or −1 if none.

in nums1 = [4,1,2], nums2 = [1,3,4,2]

out [-1,3,-1]

in nums1 = [2,4], nums2 = [1,2,3,4]

out [3,-1]

1 ≤ nums1.length ≤ nums2.length ≤ 1000
0 ≤ values ≤ 10⁴, all distinct
Follow-up: O(nums1.length + nums2.length)

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternMonotonic stack Hash lookup (seen before?)

Answer the question once for every value in nums2 with a monotonic stack, store it in a map, then each nums1 query is a lookup.

solutions

From brute force to optimal

For each query, locate it in nums2 and scan to its right.

For each x in nums1: find its index j in nums2.
Scan nums2[j+1..] for the first value > x.

timeO(m·n)

m queries, each scanning up to n elements of nums2.

spaceO(1) extra

Only the output.

javajava.util.*

1class Solution {2    public int[] nextGreaterElement(int[] nums1, int[] nums2) {3        int[] ans = new int[nums1.length];4        for (int i = 0; i < nums1.length; i++) {5            int j = 0;6            while (nums2[j] != nums1[i]) j++;          // find it in nums27            ans[i] = -1;8            for (int k = j + 1; k < nums2.length; k++) { // scan right for something bigger9                if (nums2[k] > nums1[i]) { ans[i] = nums2[k]; break; }10            }11        }12        return ans;13    }14}

One pass over nums2 fills value → next greater. Distinct values make the value a safe key.

For each x in nums2: while stack top < x, map[pop()] = x. Push x.
For each query: map.getOrDefault(x, −1).

timeO(m + n)

Each nums2 value is pushed and popped at most once; each query is an O(1) average map lookup.

spaceO(n)

The map and the stack.

javajava.util.*

1class Solution {2    public int[] nextGreaterElement(int[] nums1, int[] nums2) {3        Map<Integer, Integer> nextGreater = new HashMap<>(); // value -> its next greater value4        Deque<Integer> stack = new ArrayDeque<>();           // values waiting for an answer5        for (int x : nums2) {6            while (!stack.isEmpty() && stack.peek() < x) {7                nextGreater.put(stack.pop(), x);8            }9            stack.push(x);10        }11        int[] ans = new int[nums1.length];12        for (int i = 0; i < nums1.length; i++) {13            ans[i] = nextGreater.getOrDefault(nums1[i], -1);14        }15        return ans;16    }17}

sim

The stack part, step by step

loading simulation…

javajava.util.*

1class NextGreater {2    /** ans[i] = first value to the right of i that is bigger than nums[i], or -1. */3    static int[] nextGreater(int[] nums) {4        int n = nums.length;5        int[] ans = new int[n];6        Arrays.fill(ans, -1);7        Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting; values decrease bottom -> top8        for (int i = 0; i < n; i++) {9            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {10                ans[stack.pop()] = nums[i]; // nums[i] is the answer for the popped index11            }12            stack.push(i);13        }14        return ans; // whoever is still waiting keeps -115    }16}

in the room

How to say it in the interview

talk track

Notice the subset structure: "I'll precompute answers for all of nums2, then look up the queries."
Point out that pushing values (not indices) is fine here because values are distinct and we only need the value.

traps

Looking for the next greater value in nums1 — the search happens in nums2.
map.get(x) for a value that was never popped returns null, and unboxing it into an int throws. Use getOrDefault(x, -1).
Using Stack instead of ArrayDeque — it works, but Stack is synchronized and slower.

what they ask next

Follow-ups

What if values could repeat?

Store answers by index (int[] for nums2) and map each query to its index — or answer queries by position directly.

before you submit

Edge cases to test

The biggest value never gets an answer: −1.
The answer can be far away: in [9, 5, 0, 7], the next greater of 5 is 7, not 0.
A falling nums2 gives −1 for every query.

practise next