Sparse table & binary search
Complexity\n- Time complexity:\nO(nlog(n))\nin the general problem when searching for the k-th greater element, the complexity would be O(nlog(n)k)\n\n\n- Space
# Complexity\n- Time complexity:\n$$O(n*log(n))$$\nin the general problem when searching for the k-th greater element, the complexity would be $$O(n*log(n)*k)$$\n\n\n- Space complexity:\n$$O(n*log(n))$$, both for the general problem when searching for the k-th greater element\n\n\n# Code\n```\ntemplate<typename T, typename D>\nclass sparse_table {\nprivate:\n    size_t n;\n    size_t logn;\n    vector<vector<D>> table;\n    vector<size_t> lg;\n\n    D (*convert)(const T &);\n\n    T (*function)(const T &, const T &);\n\npublic:\n    sparse_table(const vector<T> &arr, D (*conv)(const T &), T (*func)(const T &, const T &)) : n(arr.size()),\n                                                                                                logn(log2(n) + 1),\n                                                                                                convert(conv), function(func) {\n        table.resize(logn, vector<T>(n));\n        for (size_t i = 0; i < n; i++)\n            table[0][i] = convert(arr[i]);\n\n        for (size_t k = 1; k < logn; k++)\n            for (size_t i = 0; i + (1 << k) <= n; i++)\n                table[k][i] = function(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);\n\n        // lg[i] stores and biggest i such that\n        // 2^i is smaller or equal to i\n        lg.resize(n + 1);\n        for (size_t i = 1; i <= n; i++)\n            lg[i] = std::__bit_width(i) - 1;\n    }\n\n    // query that merges two (may) overlapping ranges\n    T query_overlap(size_t l, size_t r) { // [l, r)\n        size_t pow = lg[r - l];\n\n        return function(\n                table[pow][l],\n                table[pow][r - (1 << pow)]\n        );\n    }\n\n    // qeury that merges non overlapping ranges\n    T query_nooverlap(size_t l, size_t r) { // [l, r)\n        bool empty = true;\n        T ans;\n\n        size_t curr_l = l;\n        for (ssize_t k = logn - 1; k >= 0; k--) {\n            size_t sz = 1 << k;\n\n            if (sz <= r - curr_l) {\n                if (empty) {\n                    ans = table[k][curr_l];\n                    empty = false;\n                } else\n                    ans = function(ans, table[k][curr_l]);\n\n                curr_l += sz;\n            }\n        }\n\n        return ans;\n    }\n\n};\n\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n\n        auto conv = [](const int &val) { return val; };\n        auto func = [](const int &left, const int &right) { return max(left, right); };\n        sparse_table<int, int> table(nums, conv, func);\n\n        vector<int> second_next_greater(n);\n        for (int i = n - 1; i >= 0; i--) {\n            // search the first next greater element\n            int low_first = i + 1;\n            int high_first = n;\n            while (low_first < high_first) {\n                int mid = low_first + (high_first - low_first) / 2;\n\n                if (table.query_overlap(i + 1, min(n, mid + 1)) <= nums[i])\n                    low_first = mid + 1;\n                else\n                    high_first = mid;\n            }\n            if (!(low_first < n)) {\n                second_next_greater[i] = -1;\n                continue;\n            }\n\n            // search the second next greater element\n            int low_second = low_first + 1;\n            int high_second = n;\n            while (low_second < high_second) {\n                int mid = low_second + (high_second - low_second) / 2;\n\n                if (table.query_overlap(low_first + 1, min(n, mid + 1)) <= nums[i])\n                    low_second = mid + 1;\n                else\n                    high_second = mid;\n            }\n            if (!(low_second < n)) {\n                second_next_greater[i] = -1;\n                continue;\n            }\n\n            second_next_greater[i] = nums[low_second];\n        }\n\n        return second_next_greater;\n    }\n};\n```
['C++']