Python3 || binary search || O(n^2)
Complexity\n- Time complexity:\n~~O(nlog(n))~~\nO(n^2)\n\n- Space complexity:\nO(n)\n\n# Intuition\ncomputing the number of elements greater can be done in $O(l
# Complexity\n- Time complexity:\n~~O(nlog(n))~~\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Intuition\ncomputing the number of elements greater can be done in $O(log(n))$ if the list is sorted using binary search\n\n# Approach\nwe need $arr1$ and $arr2$ to construct $result$. in addition, we can have sorted versions of $arr1$ and $arr2$, which are $sorted1$ and $sorted2$\n\n\n\n# Code\n```\nclass Solution:\n    def resultArray(self, nums: List[int]) -> List[int]:\n        arr1, arr2 = [nums[0]], [nums[1]]\n        sorted1, sorted2 = [nums[0]], [nums[1]]\n\n        def binary_search(arr, val):\n            left, right = 0, len(arr)-1\n            while left <= right:\n                mid = left + (right - left) // 2\n                if arr[mid] == val:\n                    while mid < len(arr) and arr[mid] == val:\n                        mid += 1\n                    return mid\n                elif arr[mid] < val:\n                    left = mid + 1\n                else:\n                    right = mid - 1\n            return left\n\n        for i in range(2, len(nums)):\n            val = nums[i]\n            index1, index2 = binary_search(sorted1, val), binary_search(sorted2, val)\n            count1, count2 = len(arr1) - index1, len(arr2) - index2\n            if count1>count2 or (count1==count2 and len(arr1)<=len(arr2)): \n                arr1.append(val)\n                sorted1.insert(index1, val)\n            else:\n                arr2.append(val)\n                sorted2.insert(index2, val)\n\n        result = arr1 + arr2\n        return result\n```
['Binary Search', 'Sorting', 'Python3']