Next Greater Element I

Practice Link

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 &lt;= 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.

Intiution#

• We maintain a stack called monotonic stack (descreasing)
• Traverse the second array from the back and store the respected greater elements in map.
• Finally, we map the first array elements in the map data structure and return them.

Solution - Monotonic Stack#

Traverse nums2 right-to-left and maintain a monotonically decreasing stack of values. For each element, pop all stack entries that are smaller or equal — they cannot be the "next greater" for this element or anything to its left. The first remaining stack entry, if any, is the next greater element; store it in a hash map keyed by the current value. After one pass, every element in nums2 has its answer in the map, and nums1 answers are simply looked up in O(1) each.

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> mpp;
        stack<int> stk;

        for(int i=nums2.size()-1;i>=0;i--)
        {
            while(!stk.empty() && stk.top()<=nums2[i])
                stk.pop();

            if(!stk.empty())
                mpp[nums2[i]] = stk.top();
            else
                mpp[nums2[i]] = -1;
            stk.push(nums2[i]);
        }

        vector<int> ans;
        for(int num: nums1)
        {
            ans.push_back(mpp[num]);
        }

        return ans;

    }
};

Time Complexity: O(2n)

Space Complexity: O(n)