Segment Tree - O(nLog n) solution
Intuition\n Describe your first thoughts on how to solve this problem. \nIf the array is sorted one can find the no. of elements > curr element.\n\n# Approach\n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf the array is sorted one can find the no. of elements > curr element.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCaveat: for every operation, if you add an element and sort it to proceed with the above intuition you will get T: O(n*nlogn). To overcome this you can create a bucket of max(nums[i]).\nSince num[i] = 10^9, and we cant create a bucket of this big size.\nAnother trick would be to map the elements with the bucket index. By this you will only create a bucket of size n = 10^5.\nOnce you have the bucket you can use segment tree\'s query range approach to retrieve the elements > curr ele.\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    Map<Integer, Integer> valToI;\n    int[] tree1, tree2;\n\n    public int[] resultArray(int[] nums) {\n        int n = nums.length;\n        valToI = new HashMap<>();\n        functValToI(Arrays.copyOf(nums, n), n);\n        tree1 = new int[4 * n];\n        tree2 = new int[4 * n];\n        int[] ans = new int[n];\n        int j = 0, k = 1;\n\n        // Process the first element\n        ans[j++] = nums[0];\n        update(0, valToI.get(nums[0]), 0, n - 1, tree1);\n        nums[0] = -1;\n        update(0, valToI.get(nums[1]), 0, n - 1, tree2);\n\n        // Process the remaining elements\n        for (int i = 2; i < n; i++) {\n            int ind = valToI.get(nums[i]);\n            int a = rangeQuery(0, ind + 1, n - 1, 0, n - 1, tree1);\n            int b = rangeQuery(0, ind + 1, n - 1, 0, n - 1, tree2);\n\n            // Update trees and ans array based on conditions\n            if (a > b || (a == b && j <= k)) {\n                update(0, ind, 0, n - 1, tree1);\n                ans[j++] = nums[i];\n                nums[i] = -1;\n            } else {\n                update(0, ind, 0, n - 1, tree2);\n                k++;\n            }\n        }\n\n        // Append remaining elements to ans array\n        for (int i = 0; i < n; i++) {\n            if (nums[i] > -1)\n                ans[j++] = nums[i];\n        }\n\n        return ans;\n    }\n\n    // Function to create a mapping from value to index\n    public void functValToI(int[] nums, int n) {\n        Arrays.sort(nums);\n        for (int i = 0; i < n; i++) {\n            if (!valToI.containsKey(nums[i])) {\n                valToI.put(nums[i], i);\n            }\n        }\n    }\n\n    // Function to update the segment tree\n    public void update(int i, int ind, int l, int r, int[] tree) {\n        if (l == r) {\n            tree[i]++;\n            return;\n        }\n\n        int mid = l + (r - l) / 2;\n        if (mid >= ind)\n            update(2 * i + 1, ind, l, mid, tree);\n        else\n            update(2 * i + 2, ind, mid + 1, r, tree);\n\n        tree[i] = tree[2 * i + 1] + tree[2 * i + 2];\n    }\n\n    // Function to perform range query on the segment tree\n    public int rangeQuery(int i, int x, int y, int l, int r, int[] tree) {\n        if (l >= x && r <= y)\n            return tree[i];\n\n        if (Math.min(r, y) < Math.max(l, x))\n            return 0;\n\n        int mid = l + (r - l) / 2;\n        return rangeQuery(2 * i + 1, x, y, l, mid, tree) + rangeQuery(2 * i + 2, x, y, mid + 1, r, tree);\n    }\n}\n\n```
['Java']