Code Implementation

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        stack = []
        next_greater = {}
        for num in nums2:
            while stack and num > stack[-1]:
                prev = stack.pop()
                next_greater[prev] = num
            stack.append(num)
        while stack:
            next_greater[stack.pop()] = -1
        return [next_greater[num] for num in nums1]
      

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> next_greater;
        stack<int> st;
        for (int num : nums2) {
            while (!st.empty() && num > st.top()) {
                next_greater[st.top()] = num;
                st.pop();
            }
            st.push(num);
        }
        while (!st.empty()) {
            next_greater[st.top()] = -1;
            st.pop();
        }
        vector<int> res;
        for (int num : nums1) {
            res.push_back(next_greater[num]);
        }
        return res;
    }
};
      

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }
        while (!stack.isEmpty()) {
            nextGreater.put(stack.pop(), -1);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreater.get(nums1[i]);
        }
        return res;
    }
}
      

var nextGreaterElement = function(nums1, nums2) {
    let stack = [];
    let nextGreater = {};
    for (let num of nums2) {
        while (stack.length && num > stack[stack.length - 1]) {
            nextGreater[stack.pop()] = num;
        }
        stack.push(num);
    }
    while (stack.length) {
        nextGreater[stack.pop()] = -1;
    }
    return nums1.map(num => nextGreater[num]);
};
      

Problem Description

Given two integer arrays nums1 and nums2, where nums1 is a subset of nums2, the task is to find the "next greater element" for each element in nums1 with respect to nums2.

The "next greater element" for an element x in nums2 is the first element to the right of x in nums2 that is greater than x. If there is no such element, the answer should be -1.

Return an array of answers for each element in nums1. Each input will have exactly one valid answer, and you must not reuse elements from nums2 for multiple queries.

Thought Process

At first glance, you might think to simply, for each element in nums1, search for its position in nums2 and then scan to the right to find the next greater element. This would work, but it would be inefficient, especially if the arrays are large.

To optimize, consider that the "next greater element" problem is a classic use case for a stack. By pre-processing nums2 and storing the next greater element for every number, we can answer each query in nums1 instantly. This is a shift from repeated searching to a one-time scan and constant-time lookups.

Think of it like preparing a cheat sheet: once you have the answer for every possible number in nums2, you can answer any question about nums1 instantly.

Solution Approach

• Step 1: Use a stack to process nums2 from left to right.
• Step 2: For each number in nums2:
  • While the stack is not empty and the current number is greater than the number at the top of the stack, the current number is the "next greater" for the number at the top. Pop the stack and record this relationship in a hash map.
  • Push the current number onto the stack.
• Step 3: After processing, any numbers left in the stack do not have a next greater element, so map them to -1.
• Step 4: For each element in nums1, look up its next greater element from the hash map and collect the answers.

The stack ensures that every number is processed just once, and the hash map allows for instant lookups, making the solution efficient.

Example Walkthrough

Let's use the example: nums1 = [4,1,2], nums2 = [1,3,4,2]

1. Process nums2:
   • Start with an empty stack and empty map.
   • See 1: stack is empty, push 1.
   • See 3: 3 > 1, so 3 is next greater for 1. Pop 1, map 1 → 3. Push 3.
   • See 4: 4 > 3, so 4 is next greater for 3. Pop 3, map 3 → 4. Push 4.
   • See 2: 2 < 4, so just push 2.
2. After finishing, stack contains 4, 2. They have no next greater, so map 4 → -1 and 2 → -1.
3. Now, for nums1:
   • 4: mapped to -1
   • 1: mapped to 3
   • 2: mapped to -1
4. Final answer: [-1, 3, -1]

Time and Space Complexity

• Brute-force: For each element in nums1, you may scan almost all of nums2 to the right, leading to O(m * n) time, where m is length of nums1 and n is length of nums2.
• Optimized: We scan nums2 once (O(n)) and build a hash map. Then we build the answer for nums1 in O(m). Thus, total time is O(m + n).
• Space Complexity: The hash map and stack may require up to O(n) space in the worst case.

The optimized approach is much more efficient and scalable for large inputs.

Summary

By leveraging a stack and a hash map, we efficiently solve the Next Greater Element I problem in linear time. The key insight is to preprocess nums2 so that every query about nums1 can be answered instantly. This approach avoids repeated scans and makes the solution both elegant and practical for large datasets.