Segment Tree || CPP || O(n * log(n))
How to find a index j such that j > i and nums[j] > nums[i] and if there are many possible indices j find the smallest one.\n\nWe can use a stack for this probl
How to find a index **j** such that **j > i** and **nums[j] > nums[i]** and if there are many possible indices **j** find the smallest one.\n\nWe can use a stack for this problem but it is also possible to do it with a segment tree lets see how, suppose we build our segment tree of **max** operation.\n\nNow suppose you are in a range of your segment tree represented by **[l, r]** now first check the maximum value in the left tree i.e **[l, mid]** if the maximum in the left tree is greater than **nums[i]** then answer lies in the left tree otherwise answer lies in the right tree i.e **[mid + 1, r]**, so keep going down in the tree until the point **l == r** and the index **j** such that **nums[i] < nums[j]** is **l**.\n\nSo first find the first index such that **k** such that **nums[i] < nums[k]** in the range **[i + 1, n]** using segment tree then find the second index **j** such that **nums[i] < nums[j]** in the range **[k + 1, n]**.\nAnd if either **k** or **j** is not present the answer for index **i** is **-1**.\n\n**Time complexity: O(n * log(n))**\n**Space complexity: O(n)**\n\n```\nclass Solution {\npublic:\n    vector<int> seg;\n    void build(int l, int r, int x, vector<int> &nums) {\n        if(l == r) {\n            if(l < nums.size()) {\n                seg[x] = nums[l];\n            }\n            return;\n        }\n\n        int mid = (l + r) / 2;\n        build(l, mid, 2 * x + 1, nums);\n        build(mid + 1, r, 2 * x + 2, nums);\n\n        seg[x] = max(seg[2 * x + 1], seg[2 * x + 2]); //Segment tree for max operation\n    }\n    int query(int k, int l, int x, int lx, int rx) {\n        if(seg[x] <= k or rx < l) return -1; \n\t\t// if the maximum in the range is less than or equal to nums[i] or the range less than i return -1\n\t\t\n        if(lx == rx) return lx;\n\n        int mid = (lx + rx) / 2;\n\n        int res = query(k, l, 2 * x + 1, lx, mid);\n\t\t//first search in the left subtree\n\t\t\n        if(res == -1) // if not present search in the right subtree\n            res = query(k, l, 2 * x + 2, mid + 1, rx);\n\t\t\t\n        return res;\n    }\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        int x = 1;\n        \n        while(x <= n) x *= 2;\n        seg.resize(2 * x, 0);\n        build(0, x - 1, 0, nums);\n        \n        vector<int> res(n, -1);\n        \n        for(int i = 0; i < n; ++i) {\n            int first = query(nums[i], i + 1, 0, 0, x - 1); //first index k such that nums[i] < nums[k]\n            if(first != -1) {\n                int second = query(nums[i], first + 1, 0, 0, x - 1); //second index j such that nums[i] < nums[j]\n                if(second != -1) res[i] = nums[second];\n            }\n        }\n        return res;\n    }\n};\n```
['Tree']