[Python 3] SortedList O(n * log(n))
The idea is to process numbers in increasing order. For example: [3,2,2,4,0,9,6,6]\nWe process from 0 -> 2 -> 3 -> 4 -> 6 -> 9:\n 0: remove its index set [4] ->
The idea is to process numbers in increasing order. For example: [3,2,2,4,0,9,6,6]\nWe process from 0 -> 2 -> 3 -> 4 -> 6 -> 9:\n* 0: remove its index set [4] -> SortedList([0, 1, 2, 3, 5, 6, 7]) -> binary search to find 2nd index greater than 4 -> 6\n* 2: remove its index set [1, 2] -> SortedList([0, 3, 5, 6, 7]) -> binary search to find 2nd index greater than 1 -> 5, 2 -> 5 \n* 3: remove its index set [0] -> SortedList([3, 5, 6, 7]) -> binary search to find 2nd index greater than 0 -> 5\n* 4: remove its index set [3] -> SortedList([5, 6, 7]) -> binary search to find 2nd index greater than 3 -> 6\n* 6: remove its index set [6, 7] -> SortedList([5]) -> binary search to find 2nd index greater than 6 -> -1, 7 -> -1\n* 9: remove its index set [5] -> SortedList([]) -> binary search to find 2nd index greater than 5 -> -1\n* So we get thet mapping {4: 6, 1: 9, 2: 9, 0: 9, 3: 6, 6: -1, 7: -1, 5: -1}, which means {nums[4]: 6, nums[1]: 9, ...}. We just need to return the mapping in order, i.e. {0: 9, 1: 9, 2: 9, 3: 6, 4: 6, 5:-1, 6:-1, 7:-1} -> [9, 9, 9, 6, 6, -1, -1, -1]\n```\nfrom sortedcontainers import SortedList\nclass Solution:\n    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n        \n        idx = defaultdict(list)\n        for i, x in enumerate(nums):\n            idx[x].append(i)\n        \n        r = SortedList(range(len(nums)))\n        \n        ans = {}\n        for k in sorted(idx.keys()):\n            for i in idx[k]:\n                r.remove(i)\n            for i in idx[k]:\n                j = r.bisect_left(i) + 1\n                if j < len(r):\n                    ans[i] = nums[r[j]]\n                else:\n                    ans[i] = -1\n        \n        return [ans[i] for i in range(len(nums))]\n```
[]