Next Greater Element — Algorithmics

You are given two arrays. nums2 holds distinct numbers, and nums1 is a subset of it. For each value in nums1, find the first number to its right in nums2 that is larger. If there isn’t one, the answer is -1.

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
// -> [-1, 3, -1]

The value 1 sits at index 0 of nums2, and the very next number, 3, is already bigger — so its answer is 3. The value 4 has only 2 to its right, which is smaller, so it gets -1.

The obvious approach, and why it hurts

For each value, walk right until you find something bigger:

function bruteForce(nums1: number[], nums2: number[]): number[] {
  return nums1.map(target => {
    const start = nums2.indexOf(target);
    for (let i = start + 1; i < nums2.length; i++) {
      if (nums2[i]! > target) return nums2[i]!;
    }
    return -1;
  });
}

That’s $O(n \cdot m)$ , and the waste is specific: each scan re-walks ground the previous scan already covered. Nothing is remembered between them.

One pass, with a stack of unanswered values

Walk nums2 once, left to right, keeping a stack of values that are still waiting for an answer.

When a new value arrives, it is the first larger number to the right of every smaller value on the stack. So pop them all and record the answer. Then push the new value, which now waits its own turn.

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const map = new Map<number, number>();
  const stack: number[] = [];

  for (const num of nums2) {
    while (stack.length && stack.at(-1)! < num) {
      map.set(stack.pop()!, num);
    }
    stack.push(num);
  }

  while (stack.length) {
    map.set(stack.pop()!, -1);
  }

  return nums1.map(num => map.get(num) ?? -1);
}

Why the stack is always decreasing

This is the part worth holding onto. After every iteration, the stack reads strictly decreasing from bottom to top — because the while loop removes anything that isn’t.

That invariant is what makes one pass sufficient. If the incoming value cannot resolve the top of the stack, it cannot resolve anything beneath it either, since everything beneath is larger. So the loop can stop immediately instead of inspecting the rest.

Whatever survives to the end never met a larger value, which is exactly the -1 case.

Cost

Each element of nums2 is pushed exactly once and popped at most once. The while loop looks alarming inside a for, but its total work across the whole run is bounded by the number of pushes:

T(n, m) = O(n + m) \quad\text{time}, \qquad O(m) \quad\text{space}

The lookups over nums1 are then a single hash hit each.

Where else this shows up

The same shape solves daily temperatures, largest rectangle in a histogram, trapping rain water, and stock span. The tell is always the same: you need, for each element, the nearest element on one side satisfying a comparison. When you see that, reach for a monotonic stack.