Next Greater Element I - Leetcode Solution

Next Greater Element I is a problem on LeetCode that requires finding the next greater number for each number in an array.

Problem Statement:

Given two arrays nums1 and nums2 where nums1 is a subset of nums2, find all the next greater numbers for each number in nums1 in the corresponding index in nums2. If there is no greater number, output -1 for the given number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: 4 is in nums2 but its next greater element 5 is not in nums2. 1 is in nums2 and its next greater element is 3 in nums2. 2 is in nums2 but its next greater element 3 is not in nums2.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1] Explanation: 2 is in nums2 and its next greater element is 3 in nums2. 4 is in nums2 but its next greater element 5 is not in nums2.

Solution:

To solve this problem, we can use a stack to keep track of the next greater element for each number in nums2. We first initialize an empty stack and iterate through nums2 from right to left.

For each number, we pop any elements from the stack that are less than the current number until we find a greater element or the stack becomes empty. We then add the current number to the stack.

Next, we iterate through nums1 and for each number, we find its index in nums2 using a hashmap. We then look up the corresponding element in the stack and add it to the result array.

If the stack is empty or there is no greater element for a given number, we add -1 to the result array.

Here's the complete Python code for the solution:

def nextGreaterElement(nums1, nums2): stack = [] greater = {}

for num in nums2[::-1]:
    while stack and stack[-1] <= num:
        stack.pop()
    greater[num] = stack[-1] if stack else -1
    stack.append(num)

results = []
for num in nums1:
    results.append(greater[num])
return results

nums1 = [4, 1, 2] nums2 = [1, 3, 4, 2] print(nextGreaterElement(nums1, nums2)) # [-1, 3, -1]

nums1 = [2, 4] nums2 = [1, 2, 3, 4] print(nextGreaterElement(nums1, nums2)) # [3, -1]

The time complexity of this solution is O(N + M), where N and M are the lengths of nums1 and nums2, respectively. This is because we iterate through each element in nums2 twice and each element in nums1 once. The space complexity is also O(N + M) because we use a hashmap to store the index of each number in nums2 and a stack to keep track of the next greater element.

1