DSA problem
Next Greater Element I
You are given two distinct integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each element nums1[i], find the next greater element of that value in nums2 — the first element to its right in nums2 that is strictly larger. If no such element exists, the answer for that position is -1.
A naive solution scans nums2 for every element of nums1 and then walks to its right looking for a greater value, costing O(n * m) time. While easy to write, this redundantly recomputes information about nums2 once per query.
The key insight is that the "next greater" relationship in nums2 is a property of nums2 alone — independent of nums1. So we can precompute, in a single pass, the next greater value for every element of nums2 and store the result in a hash map keyed by value (the problem states all elements are distinct). Then each nums1[i] is answered with a single O(1) lookup.
The precomputation uses a classic monotonic decreasing stack. We iterate nums2 left-to-right; while the current value is greater than the stack's top, that top has finally found its next greater element (the current value), so we pop and record the mapping. Anything still on the stack at the end has no next greater element and maps to -1. The total work is O(n + m) because each element is pushed and popped at most once.
Examples
nums1 = [4,1,2], nums2 = [1,3,4,2][-1,3,-1]nums1 = [2,4], nums2 = [1,2,3,4][3,-1]nums1 = [1,3,5,2,4], nums2 = [6,5,4,3,2,1,7][7,7,7,7,7]Constraints
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10^4
- All integers in nums1 and nums2 are unique.
- All integers of nums1 also appear in nums2.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.