496 Next Greater Element I

1. Description

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

 

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

 

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

 

constraints :

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• All integers in nums1 and nums2 are unique.
• All the integers of nums1 also appear in nums2.

2. Algorithms

We will use stack to find the first greater element that is to the right of input array. Stack has FIFO feature that can find the first element meets conditions.

 

Let's see how stack works with nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]. Algorithm will push num into stack one by one. If we meet the first greater element, then we pop the element from the stack and store them into dictionary.

 

iteration	num (nums2)	stack	dict
1		[ ]	{ }
2	1	[1, ]	{ }
3	3	[1, 3] -> pop -> [3, ]	{1 : 3}
4	4	[3, 4] -> pop -> [4, ]	{1 : 3, 3 : 4}
5	2	[4, 2]	{1 : 3, 3 : 4}

1. Start
2. Declare stack with empty stack(list).
3. Declare dic with empty dictionary.
4. Repeat the steps traversing the elements of nums2.
   1. For each num in nums2 push num to stack.
   2. If stack is not empty and current num is bigger than last element of the stack, (This means that we find the first greater element.)
      1. Store last element and current num into key : value pair in dict.
5. Declare res with empty list.
6. Repeate the steps traversing the elements of nums1 .
   1. For each num in nums1, if num is in dict, append value to res.
   2. Else, append -1 to res.
7. Return res.
8. End

3. Codes

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # stack : Data structure to find first greater element 
        # dict : dict[int], Stores relations of num in nums2 into dictionary that 
        #   - key : num in nums2 that have the first greater element 
        #   - value : the first greater element 
        # res : list[int], Stores first greater element that is to the right of array. 
        
        stack = [] 
        dict = {} 
        
        for num in nums2 : 
            # Check if stack is not empty and all element stored in stack meet the first greater element. 
            # If element don't find the first greater element, then push num into stack. 
            while stack != [] and num > stack[-1] : 
                dict[stack.pop()] = num 
            stack.append(num)
                
        res = [] 
        for num in nums1 : 
            if num in dict : 
                res.append(dict[num]) 
            else : 
                res.append(-1)
                
        return res

 

4. Conclusion