Next Greater Element I
Problem
The next greater element of a value x in nums2 is the first value to its right that is strictly greater than x; or −1 if no such value exists. Given nums1 (a subset of nums2 with unique values), return the next greater element of each nums1[i] in nums2.
nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2][-1, 3, -1]def next_greater_element(nums1, nums2):
nxt = {}
stack = []
for x in nums2:
while stack and stack[-1] < x:
nxt[stack.pop()] = x
stack.append(x)
return [nxt.get(v, -1) for v in nums1]function nextGreaterElement(nums1, nums2) {
const nxt = new Map();
const stack = [];
for (const x of nums2) {
while (stack.length && stack[stack.length - 1] < x) {
nxt.set(stack.pop(), x);
}
stack.push(x);
}
return nums1.map(v => nxt.has(v) ? nxt.get(v) : -1);
}class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> nxt = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int x : nums2) {
while (!stack.isEmpty() && stack.peek() < x) {
nxt.put(stack.pop(), x);
}
stack.push(x);
}
int[] ans = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) ans[i] = nxt.getOrDefault(nums1[i], -1);
return ans;
}
}vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> nxt;
vector<int> stack;
for (int x : nums2) {
while (!stack.empty() && stack.back() < x) {
nxt[stack.back()] = x; stack.pop_back();
}
stack.push_back(x);
}
vector<int> ans(nums1.size());
for (int i = 0; i < (int)nums1.size(); i++) ans[i] = nxt.count(nums1[i]) ? nxt[nums1[i]] : -1;
return ans;
}Explanation
For each number we want the first bigger number to its right. Instead of searching to the right for every element, we precompute the answer for all values in nums2 in one pass using a monotonic decreasing stack, then just look up each query.
We scan nums2 left-to-right. The stack holds values that are still waiting for a greater number to appear, in decreasing order. When the current value x is larger than the stack top, x is that top's next greater element, so we pop it and record nxt[popped] = x.
We keep popping every smaller waiting value, then push x. Anything left on the stack at the end never found a greater value, so it stays unanswered (treated as -1).
Finally, for each value in nums1 we look it up in the map nxt, defaulting to -1.
Example: nums2 = [1, 3, 4, 2]. Processing 3 resolves 1 → 3; processing 4 resolves 3 → 4; 2 finds nothing and stays. So for nums1 = [4, 1, 2] the answer is [-1, 3, -1].