Next Greater Element I - Solution
Solutions and explanations
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = [-1] * len(nums1)
stack = [] # Monotonic Decreasing Stack (Left to Right Scan)
nums1_idx_map = {num: idx for idx, num in enumerate(nums1)}
for idx, num in enumerate(nums2):
while stack and stack[-1] < num:
value = stack.pop()
res_idx = nums1_idx_map[value]
res[res_idx] = num
if num in nums1_idx_map:
stack.append(num)
return res
Complexity Analysis
Here, n is the length of nums1, and m is the length of nums2.
- Time Complexity:
O(n + m)– All elements in both arrays are traversed once, performing constant work for building the hashmap as well as stack push and pop operations. - Space Complexity:
O(n)– The hashmap, stack, and result array store at mostnelements.