Python3 ~ minimum brain power ~ O(nlogn): SORTED LIST
Intuition\n Describe your first thoughts on how to solve this problem. \nIMPORTANT : read descriptions under -memorize- because they will pop up frequently\n\n1
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIMPORTANT : read descriptions under -memorize- because they will pop up frequently\n\n1) Everything is intutive in this problem if we have a get_greater() function. Simply follow the directions verbadim.\n\nThe hard part is efficiently getting the num greater elemnts\n\n--- MEMORIZE THIS ---\nWe need a datastructure that has \na) efficient search: log(n)\nb) effiecient add/del: log(n)\nc) allows for duplicates\n\nSORTED LIST is your answer. \n\n2) create two sorted lists for each array, and update it as we create both arrays for the result accordingly.\n\n--- MEMORIZE THIS --- \nTo find the num greater we can use bisect_right(key), which is built into sorted list.\n\n--- Example to make it easy on your brain ---\narr = [12345] key = 3\n\nbisect_right() returns -> idx 3. \n\nidx 3 represents the furthest right index you would need to place your key so that all elements to the left of the index are less than or equal to it. Therefore elements to the right of the index are greater. \n\nQ: How to convert idx 3 to the number of elements to the right that are greater than it. \n\nA: len(arr) - 3 = # elements stricly greater\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(NLOGN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    - add n elements to a sorted set. logn time to add to a sorted set. This is straight from the documentation\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    - all your doing is storing every element. \n# Code\n```\nfrom sortedcontainers import SortedList\nclass Solution:\n    def resultArray(self, nums: List[int]) -> List[int]:\n        \n        a1 = [nums[0]]\n        a2 = [nums[1]]\n        \n        sorted_a1 = SortedList([nums[0]])\n        sorted_a2 = SortedList([nums[1]])\n        \n        for i in range(2,len(nums)):\n            n = nums[i]\n            g1 = len(sorted_a1) - sorted_a1.bisect_right(n)\n            g2 = len(sorted_a2) - sorted_a2.bisect_right(n)\n    \n            if g1 > g2:\n                a1.append(n)\n                sorted_a1.add(n)\n            elif g2 > g1:\n                a2.append(n)\n                sorted_a2.add(n)\n            else:\n                if len(a1) <= len(a2):\n                    a1.append(n)\n                    sorted_a1.add(n)\n                else:\n                    a2.append(n)\n                    sorted_a2.add(n)\n               \n                    \n        return a1+a2\n```
['Python3']