260. Next Greater Element I

Sweep nums2 with a decreasing stack. When a bigger value appears, it is the next-greater for everything smaller on the stack — record those answers in a map, then read them off for nums1.

Precompute answers for nums2

Scan nums2 left to right keeping a stack of values still waiting for a greater element (strictly decreasing). When the current value x is bigger than the stack top, x is that top's next-greater — pop and record nge[top] = x. Repeat, then push x.

Any value left on the stack at the end has no next greater → default -1. Finally map each nums1[i] through nge.

for x in nums2:
    while stack and stack[-1] < x: nge[stack.pop()] = x
    stack.append(x)
return [nge.get(v, -1) for v in nums1]

Worked example

nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1].

Complexity

• Time: O(n + m).
• Space: O(n).

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

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