< Back 496. Next Greater Element I We have two arrays, the first one is a subset of the second one. We need to return a list that correlates to the first list, containing the value of the next greater element for the value in the second list - these indices correlate from the first list to the answer list. To solve this, we create a dictionary mapping the numbers in the first list to their indices. This way we can easily recreate the answer list with the indices from the first list. Next, we iterate through each value in the list and maintain a decreasing monotonic stack. If the current element we're inspecting is greater than the items in the stack, we pop them off, accessing their indices from the mapping to correlate to the first list and the answer list, updating the answer list with the value of the number from the second list. After cleaning up the monotonic stack, we add the current value to the stack. We continue this until all values in the second array are processed. The solution is as follows: class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: n = len(nums1) mapping = {} ans = [-1] * n for i in range(n): mapping[nums1[i]] = i stack = [] for j in range(len(nums2)): while stack and stack[-1] < nums2[j]: lesser = stack.pop() if lesser in mapping: ans[mapping[lesser]] = nums2[j] stack.append(nums2[j]) return ans _ Time Complexity: O(n) - We iterate through each list once. _ Space Complexity: O(n) - We maintain the indices from the first list for each value in a dictionary.