C++ No Segment Tree No Stack Solution Using Sorting and Lower Bound | O(nlogn) Time O(n) Space
We only care about elements which are appearing after and which are greater than current element. So we iterate over the elements in decreasing order\n\nclass S
We only care about elements which are appearing after and which are greater than current element. So we iterate over the elements in decreasing order\n```\nclass Solution {\npublic:\n    \n    static bool cmp(pair<int,int> &a, pair<int,int> &b){\n        if(a.first==b.first)return a.second<b.second;\n        return a.first>b.first;\n    }\n    \n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n\t\tvector<pair<int,int>> a;\n\t\tfor(int i=0; i<n; i++) a.push_back({nums[i],i});\n\t\tsort(a.begin(), a.end(), cmp);\n        \n        vector<int> ans(n);\n        set<int> s;\n\t\tfor(int i=0; i<n; i++){\n\t\t\tint index = a[i].second;\n\t\t\tauto it=s.lower_bound(index);\n\t\t\tif(it!=s.end()) it++;\n\t\t\tif(it!=s.end()) {\n\t\t\t\tans[index]=nums[*it];\n\t\t\t}\n\t\t\telse {\n\t\t\t\tans[index]=-1;\n\t\t\t}\n\t\t\ts.insert(index);\n\t\t}\n        return ans;\n    }\n};\n```
['Sorting', 'Ordered Set']