Problem statement

You are given two distinct-valued arrays where nums1 is a subset of nums2. For each nums1[i], find its position j in nums2 and return the first element to the right of j in nums2 that is greater — or -1 if none exists.

Example 1

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

Example 2

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

Constraints

• 1 <= nums1.length <= nums2.length <= 25
• 0 <= values <= 100
• All values distinct; nums1 ⊆ nums2.

Hints for Next Greater Element I

1. Hint 1

   Compute the next-greater for EVERY element of nums2 with a monotonic stack.

2. Hint 2

   Store the answers in a map, then answer nums1 by lookup.

How to solve Next Greater Element I

Do not answer the queries one at a time. Solve the harder, more general question first — the next greater element for every entry of nums2 — in one linear pass, store the results in a hash map, then answer each nums1[i] with a lookup. Because all values are distinct, a map keyed by value is unambiguous.

Approach

1. Scan nums2 left to right with a stack of values still waiting for a greater element (decreasing from bottom to top).
2. For each x: while the stack top is smaller than x, pop it and record next[popped] = x.
3. Push x and continue.
4. Anything still on the stack at the end has no greater element to its right — leave it out of the map.
5. Map nums1 through the table, defaulting to -1 for values the map does not contain.

Why it works

A value is popped by the first later value that exceeds it: anything smaller is pushed above it without resolving it, and anything larger would have popped it sooner. So the recorded answer is the true next greater element, and the leftovers are exactly the entries with none.

Complexity

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

Pitfalls

• Do not search nums2 afresh for every element of nums1 — that is O(n · m) and misses the point of the problem.
• The distinct-values guarantee is what makes a value-keyed map legal. With duplicates you would have to key by index instead.
• Values with no greater element must default to -1; do not leave them unset.

Reference solution

Python

from typing import List

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    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

public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> next = new HashMap<>();
    Deque<Integer> st = new ArrayDeque<>();
    for (int x : nums2) {
        while (!st.isEmpty() && st.peek() < x) next.put(st.pop(), x);
        st.push(x);
    }
    int[] out = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        Integer v = next.get(nums1[i]);
        out[i] = (v == null) ? -1 : v;
    }
    return out;
}

C++

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

JavaScript

var nextGreaterElement = function(nums1, nums2) {
    const next = new Map();
    const st = [];
    for (const x of nums2) {
        while (st.length > 0 && st[st.length - 1] < x) next.set(st.pop(), x);
        st.push(x);
    }
    return nums1.map(function(x) { return next.has(x) ? next.get(x) : -1; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy