LeetCode 496: Next Greater Element I Solution

Master LeetCode problem 496 (Next Greater Element I), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

496. Next Greater Element I

Easy

Array Hash Table Stack Monotonic Stack

Problem Explanation

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:

Initialize an empty stack and a hashmap to store the mapping of the next greater element.
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.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 496 (Next Greater Element I)?

This page provides optimized solutions for LeetCode problem 496 (Next Greater Element I) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 496 (Next Greater Element I)?

The time complexity for LeetCode 496 (Next Greater Element I) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 496 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 496 in Java, C++, or Python.

Back to LeetCode Solutions