496. Next Greater Element I

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.

 

'''
[1] Brute force - accepted)

idea:
for i in range(num1):
    find index of num2, where num2[index]==ele
    find next greater index
    replace element in num1 with next greater index
    
code:
for i,val1 in enumerate(num1):
    cur_index=0
    for j in range(len(num2)):
        if val1==num2[j]:
            cur_index=j
            break
    
    next_index=-1
    for k in range(j+1,len(num2)):
        if num2[k]>num2[cur_index]:
            next_index=k
            break
    if next_index!=-1
        num1[i]=nums2[next_index]
    else:
        num1[i]=next_index

return num1

- T/C: O(m*n) # m==len(num1), n==len(num2)
- S/C: O(1)
'''

'''
[2] efficient solution)

using stack and hashmap
make hashmap, key=nums2.val, value=next greater element

hashmap={}
stack=[]

for ele in nums2:
    while len(stack) and stack[-1]<ele:
        hashmap[stack.pop()]=ele
    stack.append(ele)

for i,val in enumerate(nums1):
    nums1[i]=hashmap.get(val,-1)
    
return nums1

- T/C: O(m+n) # m==len(num1), n==len(num2)
- S/C: O(n)  # for hashmap and stack
'''

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

        for ele in nums2:
            while len(stack) and stack[-1]<ele:
                hashmap[stack.pop()]=ele
            stack.append(ele)

        for i,val in enumerate(nums1):
            nums1[i]=hashmap.get(val,-1)

        return nums1