Intuition
Intuition\nThis is a quintessential hard problem. To solve this you will need to use bit trees.\n\nWe do the following:\n\n1. First we create a compressed versi
# Intuition\nThis is a quintessential hard problem. To solve this you will need to use bit trees.\n\nWe do the following:\n\n1. First we create a compressed version of nums by eliminating duplicate numbers\n2. Then we assign rank to the numbers (rank is basically the number of numbers which are smaller than the current value which is just the current index since the numbers are sorted).\n3. In the bit operation, whenever we update, we pass the rank of the current num and the val. The value of the tree at index = rank is incremented by val. While index is less than or equal to n (since n+1 elements are present), we update the values in the btree and updating index by idx & -idx.\n\nYou might ask, but when not just do i++\n\nThat would defeat the purpose of the btree. The whole reason for the existence of the b tree is that we can efficiently extract the cumulative sum of a number in log time instead of linear time. That is its only purpose. The actual values of the numbers in the array does not mean much until you do the query operation which yeilds the cumulative sum upto the number\n\nIn the brute force approach, the time complexity is n^2 cuz each time you will calculate the number of elements greater that the current num in each of the 2 sub arrays. Using b trees, the search operation can be done in log(n) time. \n\nUsing brute force, appending = O(1) and search = O(n)\nUsing btrees, appending = O(log(n)), search = O(log(n))\n\nSince we will be doing appending and searching for all the elements in num, \n\ntime complexity in b tree = $$O(nlog(n)+log(n))$$\ntime complexity in brute force = $$O(n*n)$$ = $$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```golang []\n\nfunc resultArray(nums []int) []int {\n\td := compress(nums)\n\n\trank := make(map[int]int)\n\n\tfor i, v := range d {\n\t\trank[v] = i\n\t}\n\n\tbit1 := BIT{make([]int, len(d)+1), len(d) + 1}\n\tbit2 := BIT{make([]int, len(d)+1), len(d) + 1}\n\tarr1 := make([]int, 0)\n\tarr2 := make([]int, 0)\n\n\tarr1 = append(arr1, nums[0])\n\tarr2 = append(arr2, nums[1])\n\n\tbit1.update(rank[nums[0]], 1)\n\tbit2.update(rank[nums[1]], 1)\n\n\tfor i := 2; i < len(nums); i++ {\n\t\tnum := nums[i]\n\n\t\tq1 := len(arr1) - bit1.query(rank[num])\n\t\tq2 := len(arr2) - bit2.query(rank[num])\n\n\t\tif q1 > q2 || (q1 == q2 && len(arr1) <= len(arr2)) {\n\t\t\tbit1.update(rank[num], 1)\n\t\t\tarr1 = append(arr1, num)\n\t\t} else {\n\t\t\tbit2.update(rank[num], 1)\n\t\t\tarr2 = append(arr2, num)\n\t\t}\n\t}\n\n\tresult := append(arr1, arr2...)\n\treturn result\n}\n\nfunc compress(nums []int) []int {\n\td := make([]int, len(nums)+1)\n\tcopy(d, nums)\n\n\tsort.Ints(d)\n\n\tcurr := 0\n\tfor i := 1; i < len(d); i++ {\n\t\tif d[i] != d[curr] {\n\t\t\tcurr++\n\t\t\td[curr] = d[i]\n\t\t}\n\t}\n\n\treturn d[:curr+1]\n}\n\ntype BIT struct {\n\ttree []int\n\tn    int\n}\n\nfunc (this *BIT) update(index, val int) {\n\tindex++ // Increment index because BIT is 1-indexed\n\n\tfor index < this.n {\n\t\tthis.tree[index] += val\n\t\tindex += index & -index\n\t}\n}\n\nfunc (this *BIT) query(idx int) int {\n\tidx++\n\tsum := 0\n\n\tfor idx > 0 {\n\t\tsum += this.tree[idx]\n\t\tidx -= idx & -idx\n\t}\n\n\treturn sum\n}\n\n```
['Go']