Kotlin Fenwick Tree (Binary Indexed Tree)
Intuition\nThis is a perfect usecase for a Fenwick Tree,  since we need to have the algorithm run in O(nlogn) and we need to query a range for a sum. \n\nWe cou
# Intuition\nThis is a perfect usecase for a Fenwick Tree,  since we need to have the algorithm run in $$O(nlogn)$$ and we need to query a range for a sum. \n\nWe could also a Segment Tree, or some kind of "Multi Set/Tree Set/Ordered Set" (Like an ordered_set in C++) that allows duplicates, or keeping a list and running binary search over it. But of all the four options, Fenwick Tree is the simplest to implement in terms of code complexity.\n\nWe will be using our Fenwick Tree to keep track of count of items  instead in a range, instead of some kind of range sum value. In other words, sum range method should return number of elements in that range. \n\nOther than using a Fenwick Tree, the solution is straighforward. At each `num` in `nums`, from `i == 2 up to n (non-inclusive)`, we count the size of each tree, and update the trees (and result arrays) accordingly to our constraints.\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n- Space complexity: $$O(m)$$ where `m` is the max number in `nums`. \n\n**Some notes on complexity:**\n\nRunning some kind of Ordered Set should get us a space complexity of $$O(nlogn)$$ instead of $$O(m)$$. We have `3 <= n <= 10^5`and `1 <= m <= 10^9` so Fenwick tree solution gives us a slightly worse space complexity. However, Fenwick Tree should give us a better time complexity over the other solutions I tried to implement, where time complexity was $$O(n^2)$$ (In Kotlin / Java) according to my own analysis. Please do correct me if I am wrong.\n\n\n# Code\n```\nclass Solution {\n    fun resultArray(nums: IntArray): IntArray {\n        val arr1 = mutableListOf<Int> ()\n        val arr2 = mutableListOf<Int> ()\n\n        val max = nums.max() ?: 0\n\n        val f1 = FenwickTree (max + 1)\n        val f2 = FenwickTree (max + 1)\n\n        arr1.add(nums[0])\n        f1.update(nums[0])\n        arr2.add(nums[1])\n        f2.update(nums[1])\n\n        for (j in 2 until nums.size) {\n            val i = nums[j]\n            val count1 = f1.range(nums[j] + 1, max)\n            val count2 = f2.range(nums[j] + 1, max)\n\n            if (count1 > count2) {\n                arr1.add(nums[j])\n                f1.update(nums[j])\n            } else if (count2 > count1) {\n                arr2.add(nums[j])\n                f2.update(nums[j])\n            } else if (arr1.size > arr2.size) {\n                arr2.add(nums[j])\n                f2.update(nums[j])\n            } else {\n                arr1.add(nums[j])\n                f1.update(nums[j])\n            }\n        }\n\n        return (arr1 + arr2).toIntArray()\n    }\n}\n\nclass FenwickTree(val size: Int) {\n    val arr = mutableMapOf<Int, Int> ()\n\n    fun range(a: Int, b: Int): Int {\n        return range(b) - range(a - 1)\n    }\n\n    fun range(i: Int): Int {\n        var sum = 0\n        var i = i\n        \n        while (i > 0) {\n            sum += arr[i] ?: 0\n            i -= i and (-i)\n        }\n\n        return sum\n    }\n\n    fun update(i: Int) {\n        var i = i\n        while (i <= size) {\n            arr[i] = (arr[i] ?: 0) + 1\n            i += i and (-i)\n        }\n    }\n}\n```
['Kotlin']