< 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.