496 Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

• All elements in nums1 and nums2 are unique.

• The length of both nums1 and nums2 would not exceed 1000.

The Idea: Because we know that nums1 is a subset in nums2, if we can map that next greatest number in num2, then we also know this will be the next greatest number in nums1. In order to find the next greatest number in linear time, we may use a stack. This stack is going to collectively contain elements in ascending order. Iterating through the array for every element n, if we find that the top of the stack contains an element that is less than nums, then we know that n the is closest candidate that is greater than closest element which is the top of the stack. Furthermore, because previous elements in the stack have not been the next greatest element for each other, we can continue popping from the stack until n not longer holds as the next greatest element. Finally, we append the each number into the stack, because the goal is find the next greatest element for every n.

Some elements may still remain in the stack. These elements do not contain a next greater element. In this way, if they are not contained in hashmap then we know they do not have a next greater element.

Complexity: O(n) time and space

def nextGreatestNum(self, nums):
    stack = []
    hash = {}
    for n in nums:
        while stack and stack[-1] < n:
            hash[stack[-1]] = n
            stack.pop()
        stack.append(n)
    return hash

def nextGreaterElement(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """

    hash = self.nextGreatestNum(nums2)
    return [hash[i] if i in hash else -1 for i in nums1]