Skip to main content

Next Greater Element I

Problem​

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
void insert(int temp, stack<int>& st) {
    if (st.size() == 0) {
        st.push(temp);
        return;
    }
    if (st.top() > temp) {
        int t = st.top();
        st.pop();
        insert(temp, st);
        st.push(t);
    } else {
        st.push(temp);
    }
}
void sortStack(stack<int>& st) {
    class Solution {
       public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            int n = nums2.size();
            unordered_map<int, int> mp;
            for (int j : nums1) {
                int indx = 0;
                while (nums2[indx] != j) indx++;
                while (indx < n && nums2[indx] <= j) indx++;
                if (indx < n) mp[j] = nums2[indx];
            }
            vector<int> ans;
            for (auto j : nums1)
                ans.push_back(mp.find(j) != mp.end() ? mp[j] : -1);
            return ans;
        }
    };
    if (st.size() == 1) return;
    int temp = st.top();
    st.pop();
    sortStack(st);
    insert(temp, st);
}