Crack the Backend

Problem Statement

nums1 and nums2 are two arrays; nums1 is a subset of nums2. For each element nums1[i], find the next greater element in nums2: the first element to the right of nums1[i]'s position in nums2 that is strictly greater. If there is no such element, use -1. Return an array answer where answer[i] is the next greater element for nums1[i].

Key Observations

Monotonic stack (decreasing): Scan nums2 left to right. Keep a stack of "not yet assigned NGE" values. When we see a value x greater than the stack top, the NGE of the stack top is x — pop and record in a map. Then push x. This way each element is pushed and popped at most once.
Build a map num -> next greater for all elements in nums2 that have an NGE; for nums1[i] just lookup (default -1).

Approach

High-level: Run a decreasing monotonic stack on nums2. For each x: while stack not empty and x > stack.peek(), map.put(stack.pop(), x); stack.push(x). Then for each nums1[i] return map.getOrDefault(nums1[i], -1).

Steps: Map<Integer,Integer> next; Deque for stack. For x in nums2: while (!st.isEmpty() && x > st.peek()) next.put(st.pop(), x); st.push(x). Build result: for i, result[i] = next.getOrDefault(nums1[i], -1).

Implementation

Java

public 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++) {
        out[i] = next.getOrDefault(nums1[i], -1);
    }

    return out;
}

Test Cases

Example 1

Input

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

Expected

[-1,3,-1]

Explanation

NGE for 4,1,2 in nums2.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.