LeetCode 496: Next Greater Element I

Explanation

To solve this problem, we can use a stack to keep track of elements in nums2. We iterate through nums2 from right to left, and for each element, we pop elements from the stack that are less than the current element until we find an element that is greater. We store this mapping of the next greater element in a hashmap.

Then, we iterate through nums1 and for each element, we look up its corresponding next greater element from the hashmap.

Algorithm:

1. Initialize an empty stack and a hashmap to store the mapping of the next greater element.
2. Iterate over nums2 from right to left:
   • Pop elements from the stack that are less than the current element.
   • Store the next greater element in the hashmap.
3. Iterate over nums1:
   • Look up the next greater element for each element in nums1 from the hashmap.

Time Complexity:

The time complexity of this approach is O(nums1.length + nums2.length) as we iterate through both arrays once.

Space Complexity:

The space complexity is O(nums2.length) for the stack and hashmap.

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