Blog

Java Solution for Leetcode 496

Introduction

• In this article, we will solve Leetcode 496 using Java. We will solve it using a stack data structure.

Problem Statement

• The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
• You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
• For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
• Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example

Solution

Intuition

• Since we need to find the next greater element on the right side we will iterate the input array from the right side.
• By doing so, we can say for sure that the first element from the right side will always have -1 as the Next greater element since there is no greater element for the first element.
• Now we can move toward the left and now we need to search next greater element to the right from current element. now we can perform another loop to find next greater element but that would increase complexity. Another method is to keep the greater element as we see in some data structure. but we need to maintain the order as well since we are finding immediate greater element and not any greater element.
• Stack is a data structure where we can keep the last visited element in decreasing order. For example , in above diagram as soon as we see new greater element than the one at the top of the stack we pop the element from stack since its no use for us because current element is larger than the one in stack.
• Now whenever we see element that is lower than the one in stack we push to the stack. 
• If we come across element that is greater than the peek of the stack then we need to pop the element from the stack until we find next greater in the stack , or if stack get empty then we dont have greater element for that number. think about the example -> [ 10,7,8,9, 15] , our stack would be [ [15, 9,8,7] , when we reach to 10 then peak of the stack is lesser than current number and we need to scan through all the element in stack so far until we reach to the element which is greater than 10 i.e 15 so our stack becomes [ 15, 10 ] and we pop other elements. Here is the logic to achieve that.

 while(!stack.isEmpty() && stack.peek() < nums2[i]){
                stack.pop();
            }

Code

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        
        Map<Integer, Integer> map = new HashMap<>(); // need map for lookup of input nums1
        
        Arrays.stream(nums1).forEach(a->map.put(a,-1)); // initialize lookup with input nums1
        
        for(int i=nums2.length-1;i>=0;i--){ // iterate from right side 
            
            while(!stack.isEmpty() && stack.peek() < nums2[i]){ 
                stack.pop();       // if current element is greater than the top of the stack
            }                      // then we need to pop all the smaller element until we get the next greater element for curr element or stack gets emptied
            
            if(map.containsKey(nums2[i])){ // if curr num is in the look then we set the nge for it otherwise we dont need to consider it since its not asked in question
                int nge = stack.isEmpty() ? -1:stack.peek(); // check the reason of loop termination above and set either nge(in case we found one) or -1 default
                map.put(nums2[i], nge);
            }      
            stack.push(nums2[i]); // push the curr element in stack for next element
        }
        
        int[] res = new int[nums1.length];
        int i=0;
        for(int num: nums1){
            res[i++] = map.get(num); // set the result to return, we can modify nums1 and return that as well to save space
        }
        
        
        return res;
}

Result

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Conclusion

• In this article, we solve Next Greater Element 1 LC 496 using the stack data structure. This problem is a type of the monotonic stack.

Best Seller Course

If you want to upskill your coding interview game, you can definitely check out this bestseller course