Java | Time : O(nlogn) | Space : O(n) or O(logn) | Sorting, TreeSet, OrderedSet, k-th greater
\n\n//1. sort in descending order of nums[i], and ascending order of index i\n//2. create an ordered set, in Java, we use treeset\n//3. traverse the sorted arra
```\n\n//1. sort in descending order of nums[i], and ascending order of index i\n//2. create an ordered set, in Java, we use treeset\n//3. traverse the sorted array and get k-th greater element.\n\n//Example\n//[2,4,0,9,6]\n\n//1. sort\n//[[2,0],[4,1],[0,2],[9,3],[6,4]] => [[9,3],[6,4],[4,1],[2,0],[0,2]]\n\n//2. create a treeset and we traverse the above array\n\n//processing, [9,3], treeset is empty, so i = 3 has no greater element, result[i=3] = -1\n// add 3 into the treeset, treeset = {3}\n\n//processing [6,4], treeset has element {3}, but it is not after i=4, so no greater element, result[i=4] = -1\n// add 4 into the treeset, treeset = {3,4}, note that treeset stores indices.\n\n//processing [4,1], treeset has element {3,4}, and both are after i=1, first greater is i=3\n//next greater is i=4, and nums[i=4] = 6, perfect, result[i=1] = 6\n//add i=1 into the treeset, treeset = {1,3,4}\n\n//processing [2,0], treeset has element {1,3,4}, and all are after i=0, first greater is i=1,\n//next greater is i = 3, nums[i=3] = 9, result[i=0] = 9\n//add i = 0 into the treeset, treeset = {0,1,3,4}\n\n//finally, we process [0,2], treeset has element {0,1,3,4}, and i = 2 should be between 1 and 3\n//so first greater is i=3, and next greater is i=4, and nums[i=4] = 6, so result[i=2] = 4\n//add i=2 into the treeset, treeset = {0,1,2,3,4} and that is all.\n\n//finally, we get our result = [9, 6, 6, -1, -1]\n\n//this approach performs way slower than using a stack and a priority queue, but you can\n//generalize the result and can be a great follow-up question practice.\n\n//complexity is sorting and binary search, so its O(nlogn), notice that treeset uses red\n//black tree, so complexity is O(nlogn) and extra space is either O(n) or O(logn) depends on\n//the language you use, in java it is O(log n)\n\n\nclass Solution {\n    public int[] secondGreaterElement(int[] nums) {\n        int n = nums.length;\n        List<int[]> list = new ArrayList<>();\n        for(int i=0;i<n;i++)\n            list.add(new int[]{nums[i],i});\n        int[] result = new int[n];\n        Arrays.fill(result, -1);\n        \n        Collections.sort(list,(a,b)->(a[0]==b[0]?a[1]-b[1]:b[0]-a[0]));\n        TreeSet<Integer> set = new TreeSet<>();\n        for(int[] l:list){\n            int val = l[0], index = l[1];\n            Integer h = set.higher(index);\n            if(h!=null&&set.higher(h)!=null)\n                result[index] = nums[set.higher(h)];\n            \n            set.add(index);\n        }\n        return result;\n    }\n}\n\n```
['Tree', 'Sorting', 'Ordered Set']