EasyNeetCode150ArrayHash TableStackMonotonic Stack
Next Greater Element I
Find next greater element for each in nums1.
Examples
Input
nums1 = [4,1,2], nums2 = [1,3,4,2]
Output
[-1,3,-1]
4->-1, 1->3, 2->-1.
Constraints
- •
1 <= nums1.length <= nums2.length <= 1000 - •
All values unique
Approaches
For each in nums1, scan nums2.
CodeT: O(n*m) | S: O(1)
Precompute next greater for nums2.
CodeT: O(n+m) | S: O(m) hash map
def nextGreaterElement(nums1, nums2):
m={}; stack=[]
for n in nums2:
while stack and stack[-1]<n: m[stack.pop()]=n
stack.append(n)
return [m.get(n,-1) for n in nums1]Same approach.
CodeT: O(n+m) | S: O(m)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n*m) | O(1) | For each in nums1, scan nums2. |
| Monotonic Stack | O(n+m) | O(m) hash map | Precompute next greater for nums2. |
| Monotonic Stack Optimized | O(n+m) | O(m) | Same approach. |
Brute Force
T: O(n*m)S: O(1)
For each in nums1, scan nums2.
Monotonic Stack
T: O(n+m)S: O(m) hash map
Precompute next greater for nums2.
Monotonic Stack Optimized
T: O(n+m)S: O(m)
Same approach.
Common Mistakes
Not using stack
Wrong scan direction
Not precomputing