Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easymonotonic-stack

Next Greater Element I

Problem (restated)

nums1 is a subset of nums2. For each value x in nums1, find the first strictly greater element to the right of x in nums2. If none, answer is -1.

Intuition

Precompute next-greater for every value in nums2 with a decreasing monotonic stack, store results in a map, then look up each nums1 value.

Approaches

Monotonic stack on nums2 + map

Unverified

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

Idea. Scan nums2 left to right. Stack holds values waiting for a greater successor. When x beats the top, map top → x. Unresolved values stay without an entry (answer -1).

Walkthrough. nums2 = [1,3,4,2], nums1 = [4,1,2] → next map: 1→3, 3→4 → answers [-1, 3, -1].

Trade-offs. Values in nums2 are unique, so a map keyed by value is safe. Index-based stack is equivalent when you need positions.

Solution

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

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

Template connection

Classic next-greater-to-the-right. Same stack discipline as Daily Temperatures; output is the greater value, not distance.

Reflection

In nums2 the decreasing candidates sit on the stack. A greater value pops them and fills the map. nums1 only reads that map.
Why is the next greater of the last element −1? Every value in nums1 appears in nums2.
If duplicate values were allowed, the key would have to be the index, not the value.