Next Greater Element I

---

Intuition

• This can be solved rather trivially by checking the next element for each element in nums2, if it is in nums1.
• Instead of getting the index of nums2 of every element in nums1 (since elements are guaranteed to be unique), we instead can use a HashMap with the keys as the num in nums1, and slot in to the correct index of res accordingly.
• As a runtime improvement, we utilize the idea of a Monotonic Stack:
  • An element, if it is in nums1, is also in nums2. However, the next greater element to the element in nums1 that is also in nums2 need not be in nums1.
  • Therefore, we use the stack to compare each element in nums2 to the elements before it.
  • If an element is on the stack, this means:
    • It is in nums1.
    • It is monotonically decreasing
      • Monotonic Array
    • This is because we remove all elements on the stack that the current element is greater than. If all the elements greater than the current element remain, then those elements must still find a next greater element.
  • For every element we pop from the stack, we know it is less than the current element. And since our stack is monotonically decreasing, every element popped cannot be less than anything but the current element, meaning the next greater element is always the current index of nums2.

Complexity

Runtime

• Brute force $O(m\times n)$, since for all m elements in nums1, you must check an arithmetic series worth of elements in nums2.
• Optimized $O(m+n)$, since there can be at most n nums2 elements in the stack total.

Space

$O(n)$, where n is the number of elements in nums2 which is the maximum that can be in res or stack, respectively.

Code

Monotonic Stack

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res1Idx = {num:i for i, num in enumerate(nums1)}
        res = [-1] * len(nums1)
        stack = []
 
        for i in range(len(nums2)):
            while stack and nums2[i] > stack[-1]:
                val = stack.pop()
                idx = res1Idx[val]
                res[idx] = nums2[i]
            if nums2[i] in res1Idx:
                stack.append(nums2[i])
        
        return res

Brute Force without index()

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res1Idx = {num:i for i, num in enumerate(nums1)}
        res = [-1] * len(nums1)
 
        for i in range(len(nums2)):
            if nums2[i] not in res1Idx:
                continue
            for j in range(i + 1, len(nums2)):
                if nums2[i] < nums2[j]:
                    res[res1Idx[nums2[i]]] = nums2[j]
                    break
        
        return res

• This takes advantage of the fact that all numbers in nums1 and nums2 are unique, so you can use the subset nums1 as the key in your hashmap as an alternative to index.
• This doesn’t really speed up the runtime when compared to the traditional brute force approach.

Brute Force

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        indices = [nums2.index(num) for num in nums1]
        res = [-1] * len(nums1)
 
        count = 0
        for i, idx in enumerate(indices):
            for num in nums2[idx + 1:]:
                if nums2[idx] < num:
                    res[i] = num
                    break
        
        return res

Notes

Cards

START Basic Front: Next Greater Element I Back: Use a Monotonic Stack that is monotonically decreasing.

END

---

References

• Next Greater Element I