Next Greater Element I Leetcode Solution

Table of Contents

Problem Statement

Next Greater Element I Leetcode Solution – 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 1:

Input:

 nums1 = [4,1,2], nums2 = [1,3,4,2]

Output:

 [-1,3,-1]

Explanation:

 The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input:

 nums1 = [2,4], nums2 = [1,2,3,4]

Output:

 [3,-1]

Explanation:

 The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints:

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10⁴
All integers in nums1 and nums2 are unique.
All the integers of nums1 also, appear in nums2.

Follow up: Could you find an O(nums1.length + nums2.length) solution?

Approach

Idea:

we make a map to store every element’s next greater element
to find the next greater element in nums2 we maintain a monotonically increasing stack
to do this we traverse the nums2 array from (n-1 to 0 where n is the size of nums2)
if the stack is not empty, then compare its top element with nums2[i]
if the nums2[i] is greater than stack’s top element, then we pop from stack while (!st.empty() && st.top()>nums2[i] )
now if we find an element in the stack then we store it in the map
otherwise, we store -1 in the map
now we push nums2[i] into the stack as it might be the next greater element for elements ranges b/w (i-1 to 0)

C++ Program of Next Greater Element I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
     
        map<int,int> mp;
        stack<int> st;
        
        for(int i=nums2.size()-1;i>=0;i--)
        {
            while(!st.empty() && st.top()<nums2[i])
                st.pop();
            
            if(st.empty())
                mp[nums2[i]]=-1;
            else
                mp[nums2[i]]=st.top();
            
            st.push(nums2[i]);
            
        }
        
        for(int i=0;i<nums1.size();i++)
        {
            nums1[i]=mp[nums1[i]];
        }
        
        return nums1;
        
        
        
    }
};

Java Program of Next Greater Element I

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

Complexity Analysis for Next Greater Element I Leetcode Solution

Time Complexity

O(n+m) where n is the size of nums1 and m is the size of nums2

Space Complexity

O(m) as we use a map to store every element’s next element and stack to find the next greater element