What it teaches: Compute next-greater answers for one array with a monotonic stack, then look them up for another with a hash map.
Practise it on judges as “Next Greater Element I”.
The problem
nums1 is a subset of nums2 (all values distinct). For each x in nums1, find the first element to the right of x in nums2 that is greater than x, or −1.
These clues point to Monotonic Stack: Keep a stack whose values only increase (or decrease); each element pops everything it beats, finding "next greater/smaller" in one pass.
Stuck? Take one hint at a time
Solution.java · starter
import java.util.*;
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
return new int[nums1.length];
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Run the next-greater stack over nums2, recording next[value] = greater value when popping. Then answer each nums1 value from the map (default −1).
Approach 1
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() && x > stack.peek()) next.put(stack.pop(), x);
stack.push(x);
}
int[] ans = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) ans[i] = next.getOrDefault(nums1[i], -1);
return ans;
}
}
Verdict: Linear.
Before you submit
Edge cases and common mistakes
Test these inputs
Largest value (−1)
Last element of nums2 (−1)
Mistakes people make
Searching nums2 from scratch for each query: O(n · m).
Interview
Follow-up questions
What if the array is circular (search wraps around)?