Next Greater Element I

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.

Example 1:

nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

Example 2:

nums1 = [2,4], nums2 = [1,2,3,4]

Output: [3,-1]

## Problem: Next Greater Element I

Given two distinct 0-indexed integer arrays `nums1` and `nums2`, where `nums1` is a subset of `nums2`, find the next greater element for each element in `nums1` in `nums2`. The next greater element of an element `x` is the first greater element to its right in the same array. If there is no next greater element, the answer is -1.

**Example:**

`nums1 = [4, 1, 2]`
`nums2 = [1, 3, 4, 2]`

Output: `[-1, 3, -1]`

## Naive Approach

The naive approach involves iterating through `nums1` and for each element, searching for it in `nums2`. Once found, we iterate through the rest of `nums2` to find the next greater element.

```python
def next_greater_element_naive(nums1, nums2):
    result = []
    for num1 in nums1:
        found = False
        greater = -1
        for i, num2 in enumerate(nums2):
            if num1 == num2:
                found = True
            elif found and num2 > num1:
                greater = num2
                break
        result.append(greater)
    return result

# Example usage
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(next_greater_element_naive(nums1, nums2))

Time Complexity: O(m*n)

where n is the length of nums2 and m is the length of nums1. For each element in nums1, we potentially iterate through nums2 twice.

Space Complexity: O(m)

where m is the length of nums1, as we store the results in an array of size m.

Optimal Approach: Using Stack and HashMap

We can optimize this by using a stack and a hashmap. We iterate through nums2, and for each element, we pop elements from the stack that are smaller than the current element. We store the next greater element in the hashmap. Finally, we iterate through nums1 and look up the next greater element in the hashmap.

def next_greater_element_optimal(nums1, nums2):
    stack = []
    next_greater = {}
    for num in nums2:
        while stack and num > stack[-1]:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    while stack:
        next_greater[stack.pop()] = -1
        
    result = [next_greater[num] for num in nums1]
    return result

# Example usage
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(next_greater_element_optimal(nums1, nums2))

Time Complexity: O(m + n)

where n is the length of nums2 and m is the length of nums1. We iterate through nums2 once to build the hashmap and then iterate through nums1 once to look up the next greater elements.

Space Complexity: O(n)

where n is the length of nums2, as we store the next greater elements in a hashmap of size at most n.

Edge Cases

1. nums1 is empty: Return an empty array.
2. nums2 is empty: Return an empty array.
3. No next greater element exists for some elements in nums1: Return -1 for those elements.
4. nums1 contains duplicate elements: According to the prompt, this is not possible since the numbers in nums1 and nums2 are unique.
5. nums2 contains duplicate elements: According to the prompt, this is not possible since the numbers in nums1 and nums2 are unique.