Problem Description

You are given two distinct integer arrays nums1 and nums2, where nums1 is a subset of nums2 (meaning every element in nums1 also appears in nums2).

The next greater element of an element x in an array is defined as the first element that appears to the right of x and is greater than x. If no such element exists, the next greater element is -1.

Your task is to find the next greater element for each element in nums1 based on their positions in nums2.

For each element in nums1:

1. First, locate where that element appears in nums2
2. Then, find the next greater element to the right of that position in nums2
3. If a greater element exists, that's your answer; otherwise, the answer is -1

Example:

If nums1 = [4, 1, 2] and nums2 = [1, 3, 4, 2]:

• For 4: It appears at index 2 in nums2. There are no elements to its right greater than 4, so the answer is -1
• For 1: It appears at index 0 in nums2. The next greater element to its right is 3, so the answer is 3
• For 2: It appears at index 3 in nums2. There are no elements to its right, so the answer is -1

The result would be [-1, 3, -1].

The solution uses a monotonic stack approach, traversing nums2 from right to left to efficiently find the next greater element for each value, storing the results in a hash map for quick lookup when processing nums1.

Intuition

The key insight is that we need to find the next greater element for multiple queries efficiently. If we were to use a brute force approach, for each element in nums1, we'd have to find its position in nums2 and then scan rightward to find the next greater element. This would be inefficient.

Instead, we can preprocess nums2 to find the next greater element for every element in it, storing these relationships in a hash map. This way, when we need to answer queries for nums1, we can simply look up the answer in constant time.

The question becomes: how do we efficiently find the next greater element for all elements in nums2?

Consider traversing nums2 from right to left. At each position, we want to know "what is the first element to my right that is greater than me?" To answer this efficiently, we can maintain a stack that keeps track of potential candidates for being the next greater element.

The key observation is that if we have two elements where the left one is greater than the right one, the right element can never be the next greater element for any future element we process (as we move leftward). Why? Because the left element would always be a better candidate - it's both greater and closer.

This leads us to maintain a monotonic increasing stack (from top to bottom). As we traverse from right to left:

• We pop elements from the stack that are smaller than or equal to the current element (they can't be the next greater element)
• After popping, the top of the stack (if it exists) is the next greater element for the current element
• We push the current element onto the stack as it might be the next greater element for future elements we process

By processing nums2 this way, we build a complete mapping of each element to its next greater element in O(n) time. Then answering queries for nums1 becomes a simple hash map lookup.

Solution Approach

The solution uses a monotonic stack combined with a hash map to efficiently find the next greater element for all values in nums2.

Step-by-step implementation:

1. Initialize data structures:

   • stk = []: A stack to maintain potential next greater elements
   • d = {}: A hash map to store the mapping of each element to its next greater element

2. Traverse nums2 from right to left (nums2[::-1]):

   For each element x in the reversed array:

   a. Clean the stack: While the stack is not empty and the top element is less than x:

   while stk and stk[-1] < x:
       stk.pop()

   This removes all elements smaller than x because they cannot be the next greater element for any future element we process (moving leftward).

   b. Record the next greater element: After cleaning, if the stack is not empty, the top element is the next greater element for x:

   if stk:
       d[x] = stk[-1]

   If the stack is empty, x has no next greater element (we don't add it to the dictionary).

   c. Add current element to stack:

   stk.append(x)

   Push x onto the stack as it might be the next greater element for elements we'll process later.

3. Build the result: For each element in nums1, look up its next greater element in the hash map:

   return [d.get(x, -1) for x in nums1]

   Using d.get(x, -1) returns the next greater element if it exists, otherwise returns -1.

Time Complexity: O(m + n) where m = len(nums1) and n = len(nums2). Each element in nums2 is pushed and popped from the stack at most once.

Space Complexity: O(n) for the stack and hash map, which can store at most all elements from nums2.

The monotonic stack ensures that at any point, the stack contains elements in increasing order from top to bottom, representing potential candidates for being the next greater element for future elements we process.

Example Walkthrough

Let's walk through the solution with nums1 = [4, 1, 2] and nums2 = [1, 3, 4, 2].

Step 1: Process nums2 from right to left

We'll traverse nums2 in reverse order: [2, 4, 3, 1], maintaining a stack and building our hash map.

Processing element 2 (rightmost):

• Stack is empty: []
• No elements in stack, so 2 has no next greater element
• Push 2 to stack: [2]
• Hash map: {}

Processing element 4:

• Stack: [2]
• Check top: 2 < 4, so pop 2
• Stack becomes empty: []
• No elements left in stack, so 4 has no next greater element
• Push 4 to stack: [4]
• Hash map: {}

Processing element 3:

• Stack: [4]
• Check top: 4 > 3, so don't pop
• Top of stack (4) is the next greater element for 3
• Push 3 to stack: [4, 3]
• Hash map: {3: 4}

Processing element 1:

• Stack: [4, 3]
• Check top: 3 > 1, so don't pop
• Top of stack (3) is the next greater element for 1
• Push 1 to stack: [4, 3, 1]
• Hash map: {3: 4, 1: 3}

Step 2: Build result for nums1

Now we look up each element of nums1 = [4, 1, 2] in our hash map:

• For 4: Not in hash map → return -1
• For 1: Hash map has 1: 3 → return 3
• For 2: Not in hash map → return -1

Final result: [-1, 3, -1]

The stack maintains a monotonic increasing property (from top to bottom), ensuring we always have the closest greater element available for lookup.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n)

The algorithm iterates through nums2 once in reverse order, which takes O(n) time where n is the length of nums2. During this iteration, each element is pushed onto the stack exactly once and popped at most once, maintaining O(n) complexity. After building the dictionary d, the algorithm iterates through nums1 to construct the result array, which takes O(m) time where m is the length of nums1. Therefore, the total time complexity is O(n + m).

Space Complexity: O(n)

The algorithm uses a stack stk that can contain at most n elements (in the worst case when nums2 is in increasing order). Additionally, the dictionary d stores at most n key-value pairs, one for each element in nums2. The output array has size m, but this is typically not counted in space complexity analysis as it's the required output. Therefore, the space complexity is O(n) where n is the length of nums2.

Common Pitfalls

1. Traversing nums2 from left to right instead of right to left

One of the most common mistakes is attempting to traverse nums2 from left to right while building the next greater element mapping. This approach seems intuitive but leads to incorrect logic.

Incorrect approach:

# WRONG: Traversing left to right
for num in nums2:
    while stack and stack[-1] < num:
        popped = stack.pop()
        next_greater_map[popped] = num
    stack.append(num)

Problem: This approach maps elements that were popped to their next greater element, but it fails to handle elements that remain in the stack at the end (they have no next greater element). Additionally, it requires extra logic to handle these remaining elements.

Correct approach: Traverse from right to left as shown in the solution, which naturally handles all cases.

2. Incorrect stack maintenance condition

Another common mistake is using the wrong comparison operator when cleaning the stack.

Incorrect:

# WRONG: Using <= instead of <
while stack and stack[-1] <= num:
    stack.pop()

Problem: Using <= would remove equal elements from the stack, but equal elements are not "greater" elements. This would cause incorrect results when an element has a duplicate to its right but a greater element further right.

Example: If nums2 = [2, 2, 3], the first 2 should have next greater element 3, not -1.

3. Forgetting to handle missing keys in the dictionary

When building the result array, forgetting to provide a default value for elements not in the dictionary leads to KeyError.

Incorrect:

# WRONG: Direct dictionary access
return [next_greater_map[num] for num in nums1]

Problem: If an element has no next greater element, it won't be in the dictionary, causing a KeyError.

Correct approach: Use dict.get() with a default value:

return [next_greater_map.get(num, -1) for num in nums1]

4. Not understanding the monotonic property

A conceptual pitfall is not maintaining the monotonic decreasing property of the stack (when viewed from bottom to top). The stack should always contain elements in decreasing order to efficiently find the next greater element.

Key insight: When traversing right to left, any element smaller than the current element cannot be the next greater element for any future element we process, so we can safely remove it from the stack.