C++ | Stack to find NGE then using segment tree with binary search
It is inututive to do a next greater element logic , then to find out the number that is second NGE we are using a segment tree with binary search.\n\nNew to se
It is inututive to do a next greater element logic , then to find out the number that is second NGE we are using a segment tree with binary search.\n\nNew to segment tree learn it from [here](https://www.youtube.com/watch?v=NEG-SoyigGE&t=61s)\n#striverOP\n\n\n```\n// CPP code for range maximum query and updates\n#include <bits/stdc++.h>\nusing namespace std;\n\n\nint getMid(int s, int e)\n{\n\treturn s + (e - s) / 2;\n}\n\n\nint MaxUtil(int* st, int ss, int se, int l,\n\t\t\tint r, int node)\n{\n\t\n\tif (l <= ss && r >= se)\n\t\treturn st[node];\n\n\tif (se < l || ss > r)\n\t\treturn -1;\n\n\tint mid = getMid(ss, se);\n\t\n\treturn max(MaxUtil(st, ss, mid, l, r,\n\t\t\t\t\t2 * node + 1),\n\t\t\tMaxUtil(st, mid + 1, se, l,\n\t\t\t\t\tr, 2 * node + 2));\n}\n\n\nint getMax(int* st, int n, int l, int r)\n{\n\t\n\tif (l < 0 || r > n - 1 || l > r)\n\t{\n\t\treturn -1;\n\t}\n\n\treturn MaxUtil(st, 0, n - 1, l, r, 0);\n}\n\n\nint constructSTUtil(int arr[], int ss, int se,\n\t\t\t\t\tint* st, int si)\n{\n\t\n\tif (ss == se)\n\t{\n\t\tst[si] = arr[ss];\n\t\treturn arr[ss];\n\t}\n\n\tint mid = getMid(ss, se);\n\t\n\tst[si] = max(constructSTUtil(arr, ss, mid, st,\n\t\t\t\t\t\t\t\tsi * 2 + 1),\n\t\t\t\tconstructSTUtil(arr, mid + 1, se,\n\t\t\t\t\t\t\t\tst, si * 2 + 2));\n\t\n\treturn st[si];\n}\n\nint* constructST(int arr[], int n)\n{\n\n\tint x = (int)(ceil(log2(n)));\n\n\tint max_size = 2 * (int)pow(2, x) - 1;\n\n\tint* st = new int[max_size];\n\n\tconstructSTUtil(arr, 0, n - 1, st, 0);\n\n\treturn st;\n}\n\n\n\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        \n        vector<int> first;\n        stack<int> st;\n        \n        // Using the next greater element logic to find the index of next greater element \n        \n        for(int i=nums.size()-1;i>=0;i--){\n            while(st.size()>0 && nums[i]>=nums[st.top()])\n                st.pop();\n            if(st.size()==0){\n                first.push_back(-1);\n            }\n            else{\n                first.push_back(st.top());\n            }\n            st.push(i);\n        }\n        \n        reverse(first.begin(),first.end());\n        vector<int> ans;\n        \n        int n=nums.size();\n        int arr[n];\n        for(int i=0;i<n;i++){\n            arr[i]=nums[i];\n        }\n        \n        \n        int* st1 = constructST(arr, n); // contsruction of segment tree that suppourt\'s range max queries\n        \n        for(int i=0;i<nums.size();i++){\n            \n            if(first[i]==-1){\n                //Thre is no NGE then it is obvious that second NGE dont exist\n                ans.push_back(-1);\n                continue;\n            }\n            \n            long long start=first[i]+1;\n            long long end=n-1;\n            int res=-1;\n            \n            //Binary searching the value which is > nums[i] in the part of array that extends from the position of first NGE index +1 to end\n            while(start<=end){\n                long long mid=(start+end)/2;\n                \n                int got=getMax(st1, n, start, mid);\n                if(got>nums[i]){\n                    //We found the value in left part then we try to reduce search space \n                    res=got;\n                    end=mid-1;\n                }\n                else\n                    start=mid+1;\n            }\n            ans.push_back(res);\n        }\n        return ans;\n        \n    }\n};\n```
['Binary Tree']