FAANG · LeetCode #496

Next Greater Element I — three-stage drill

1The ProblemEasy

Next Greater Element I

For each value in nums1, find its next greater element in nums2.

Examples

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

constraintnums1 is a subset of nums2; values are distinct.

2The PatternTIME O(n) · SPACE O(n)

Monotonic Stack

A stack kept sorted; each new value pops everything it resolves, so each element is pushed and popped once — O(n).

Problems using this pattern

3The SolutionRESULT → [-1, 3, -1]

Step through it

1 → push (nothing bigger yet)

Step 1 / 10

Python▎stack builds the map · then look up

1def nextGreaterElement(nums1, nums2):
2    nxt, stack = {}, []
3    for x in nums2:
4        while stack and x > stack[-1]:
5            nxt[stack.pop()] = x
6        stack.append(x)
7    return [nxt.get(x, -1) for x in nums1]

why it worksOne monotonic-stack pass over nums2 finds every value's next greater (each value is resolved when a bigger one appears) and stores it in a map. Then each nums1 query is an O(1) lookup — the stack does the work once, the map reuses it.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Next Greater Element I — three-stage drill