Next Greater Element I

Problem

You have two arrays nums1 and nums2 where nums1 is a subset of nums2. For each element x in nums1, find the next greater element to its right in nums2 (or -1).

Constraints

• 1 ≤ nums1.length ≤ nums2.length ≤ 1000

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        nxt = {}
        st = []
        for x in nums2:
            while st and st[-1] < x:
                nxt[st.pop()] = x
            st.append(x)
        return [nxt.get(x, -1) for x in nums1]

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.