496. Next Greater Element I

#monotonic

Problem

Next Greater Element I - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
         // Time complexity: O(nums1.length + nums2.length), iterate through both the lists
        // Space complexity: O(nums2.length), hashmap storage
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();

        for(int num: nums2) {
            // We use decreasing monotonic stack cause, stack
            // follows LIFO structure. So when we encounter
            // "num" which is greater than stackTop, it means
            // we found next greater element for current stackTop
            while(!stack.isEmpty() && stack.peek() < num) {
                // Here the num represents next greater element
                // Key is stack.pop(), which means the next greater
                // element of current stackTop is current number
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }
        
        List<Integer> result = new ArrayList<>();

        for(int num: nums1) {
            result.add(map.getOrDefault(num, -1));
        }

        return result.stream().mapToInt(i -> i).toArray();
    }
}