algoadvance

You are given two arrays (with unique elements) nums1 and nums2 where nums1 is a subset of nums2. Find the next greater element for each element of nums1 in the corresponding positions of nums2.

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

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]

Explanation: For nums1, 4 -> -1 for nums1 because there is no next greater number in nums2 after 4. 1 -> 3 because 3 is the first number greater than 1 to its right in nums2. 2 -> -1 because there is no next greater number in nums2 after 2.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]

Explanation: For nums1, 2 -> 3 because 3 is the first number greater than 2 to its right in nums2. 4 -> -1 because there is no next greater number in nums2 after 4.

Constraints:

Strategy

To solve this problem efficiently:

  1. Use a Stack: This will help keep track of the potential candidates for “next greater element”.
  2. Use a HashMap: This will store each number from nums2 and its corresponding next greater element.
  3. Iterate through nums2 in reverse order: This allows us to efficiently determine the next greater elements using a stack.

Approach

  1. Initialize an empty stack and an empty hashmap.
  2. Traverse nums2 from right to left:
    • While the stack is not empty and the top of the stack is less than or equal to the current element, pop from the stack.
    • If the stack is not empty, the next greater element for the current element is the element on the top of the stack.
    • Otherwise, the next greater element does not exist, so we store -1.
    • Push the current element onto the stack.
  3. For each element in nums1, retrieve the next greater element from the hashmap.

Time Complexity

Code

def nextGreaterElement(nums1, nums2):
    # HashMap to store the next greater elements
    next_greater = {}
    
    # Stack to keep track of the current element and find the next greater element
    stack = []
    
    # Iterate through nums2 in reverse order
    for num in nums2[::-1]:
        # Maintain elements in stack such that they are always greater than the current element
        while stack and stack[-1] <= num:
            stack.pop()
        
        # If stack is not empty, then top of stack is the next greater element
        if stack:
            next_greater[num] = stack[-1]
        else:
            next_greater[num] = -1
        
        # Push the current element into the stack
        stack.append(num)
    
    # Build the result for nums1 based on the next_greater map
    result = [next_greater[num] for num in nums1]
    
    return result

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

This implementation uses a stack-based approach to achieve an efficient solution with a linear time complexity, making it suitable for the given constraints.

Try our interview co-pilot at AlgoAdvance.com