Problem Statement in English

You’re given an array nums1 of positive integers, which is a subset of nums2, which is another list of positive integers.

Your task is to find the next greater element of each number in nums1 to the right of its position in nums2. If there is no such element, then output -1.

Approach

We use the concept of a monotonic stack to solve this problem. Check out this problem to get a better idea of it.

We first create a hashmap of the elements in nums1 and their corresponding indices. This way we can check if an element in nums2 is present in nums1 in $O(1)$ time.

Then we iterate through nums2 and keep a monotonic decreasing stack of elements.

If the current element is greater than the top of the stack, then we pop the stack and update the answer array with the current element, by obtaining the index we must set this answer at from the hashmap.

If the current element that we’re iterating through from nums2 is present in nums1, then we add it to the stack.

Finally, we return the answer array.

Solution in Python


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        db = {}
        stack = []

        for num in nums2:
            while stack and num > stack[-1]:
                db[stack[-1]] = num
                stack.pop()

            stack.append(num)

        for x in stack:
            db[x]=-1

        res = []
        for num in nums1:
            res.append(db[num])
        return res

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most, where $n$ is the length of nums2.

  • Space: $O(n)$
    Since we store an answer array which has a length of $n$, where $n$ is the length of nums1.

Mistakes I Made

I had to look this one up, as I didn’t know the concept of monotonic stacks.

And we are done.