Next Greater Element I
Find the next greater element for each value of nums1 inside nums2 with one monotonic-stack pass over nums2 and a lookup map.
Problem Understanding
Next Greater Element I: nums1 is a subset of nums2, and all values are distinct. For each value of nums1, find it in nums2 and return the first value to its right that is greater, or -1 if there is none.
Example: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2] returns [-1, 3, -1].
The Intuition: Values Waiting for Something Bigger
Walk nums2 left to right and keep a stack of values that have not yet seen anything bigger. That stack is always decreasing, which is what makes it a monotonic stack:
- When
xarrives, every smaller value on top has just met its next greater element: pop each one and recordnext[value] = x. - Push
x; it now waits. - Values still on the stack at the end have no greater element.
nums1 only needs lookups in next. The same stack solves Daily Temperatures, which records distances instead of values.
Interactive Walkthrough
nums2 is on top with x filled; below it, the stack from bottom to top. Watch a big x pop several smaller values at once, each recording its next greater element in the panel beside the figure.
Dry Run Table
Input: nums2 = [1, 3, 4, 2]
| x | Popped | Recorded | Stack after |
|---|---|---|---|
| 1 | — | — | [1] |
| 3 | 1 | 1 → 3 | [3] |
| 4 | 3 | 3 → 4 | [4] |
| 2 | — | — | [4, 2] |
For nums1 = [4, 1, 2]: 4 and 2 were never popped, so the answer is [-1, 3, -1].
The Solution Template
Decreasing stack over nums2, then lookups. The C snippet uses an array as the map, since values are at most 10⁴.
Next Greater Element I Code
1var nextGreaterElement = function(nums1, nums2) {2 const nxt = new Map(), stack = [];3 for (const x of nums2) {4 while (stack.length && stack[stack.length - 1] < x) nxt.set(stack.pop(), x);5 stack.push(x);6 }7 return nums1.map((x) => nxt.get(x) ?? -1);8};
Edge Cases & Common Mistakes
- Last element of nums2: nothing is to its right, so it is never popped and its answer is -1.
- Strictly decreasing nums2: nothing is popped; every answer is -1.
- Using ≤ instead of <: values are distinct here, but in general only a strictly greater value counts.
- Searching nums2 per query: O(m · n); build the map in one pass instead.
Summary
Walk nums2 with a decreasing stack of values waiting for something bigger. Each new value pops the smaller ones and becomes their next greater element. Store the pairs in a map and answer nums1 by lookup. O(m + n) time.
More practice: DSA interview questions with answers · patterns cheat sheet