#496
Next Greater Element I
Easy Monotonic stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
nums1 is a subset of nums2. For each value in nums1, find the first greater value to its right in nums2, or -1.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each value, the first bigger value to its right.
Why this works: keep a stack of values still waiting; a bigger value pops them all and becomes their answer.
Example: nums2 [1, 3, 4, 2]
1 waits, 3 answers 1, 4 answers 3, 2 waitsnext: 1→3, 3→4, 4→-1, 2→-1
✦Hints open one at a time
Compute "next greater" for every value of nums2 once.
Keep a stack of values still waiting for a greater one; it stays decreasing.
↗Approach
Scan nums2. While the current value is bigger than the stack's top, that top's answer is the current value — record it in a map and pop. Push the current value. Then answer nums1 from the map.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> next = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int x : nums2) {
while (!stack.isEmpty() && stack.peek() < x) next.put(stack.pop(), x); // x answers them
stack.push(x);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) res[i] = next.getOrDefault(nums1[i], -1);
return res;
}
}!Common mistake
For each element, scanning to the right — O(n²).
Complexity
- Time: O(n + m).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon