Compressed array and fenwick tree | python
Intuition\nThe main challenge in this problem is to implement the greaterCount(arr, value) function efficiently. Given the dynamic nature of the data, a Fenwick
# Intuition\nThe main challenge in this problem is to implement the `greaterCount(arr, value)` function efficiently. Given the dynamic nature of the data, a Fenwick tree is a suitable choice for this task.\n\n# Approach\nFirst, we compress the array by mapping all the values in `nums` in such a way that when sorted, they form consecutive values. This compression ensures that the maximum value is at most equal to $n$ (or $n-1$ if the array is 0-indexed), preserving the order such that for any pair $i,j$, if $nums[i] \\leq nums[j]$, then $map[nums[i]] \\leq map[nums[j]]$. For example, given the array $[5,14,3,1,2]$, after compression, the mapping will be $[3,4,2,0,1]$. This compression can be efficiently achieved using binary search or built-in functions like `bisect_left` in Python.\n\nAfter compressing the array, we treat both arrays as frequency arrays for each possible value between $[0, n]$. The step before allows us to represent the data with at most an array of size $n$, which is essential for keep the complexity. For example, if we have `arr1 = [0,0,2,2,1,3]`, the corresponding frequency array `f` would be `[2,1,2,1,0,0,...,0]`.\n\nNow, the `greaterCount(arr, value)` function simply calculates the sum of the values in `f` from `value` up to $n$, i.e., $\\sum_{i= value+1}^{n} f[i]$. However, performing this summation with brute force at each step and updating it accordingly is inefficient. Instead, we use a Fenwick tree, also known as a binary indexed tree (BIT), which is a specialized data structure designed to efficiently update values and calculate prefix sums in an array of values.\n\n# Complexity\n- Time complexity:\n  - $O(n \\log(n))$\n- Space complexity:\n  - $O(n)$\n\n# Code\n```python\nclass Solution:\n    def resultArray(self, nums: List[int]) -> List[int]:\n        \n        n = len(nums)\n        \n        # Compress the array\n        v = sorted(nums)\n        # Actually we leave nums as it was since we need to return instead we create a map/dictionary.\n        mp = {x: bisect_left(v, x) for x in nums}\n        \n        # Initialize Fenwick tree\n        bit = [[0]*(n+2) for _ in range(2)]\n\n        # bit[0] will represent the frequency array of the mapped values in arr1 and bit[1] for arr2\n\n        \n        # Fenwick tree operations\n        def update(idx, which):\n            idx += 1 \n            \n            while idx <= n: \n                bit[which][idx] += 1\n                idx += idx & -idx \n                \n        def prefixSum(idx, which):\n            idx += 1\n            res = 0 \n            \n            while idx > 0: \n                res += bit[which][idx]\n                idx -= idx & -idx\n                \n            return res\n        \n        def sumRange(l, r, which):\n            return prefixSum(r, which) - prefixSum(l-1, which)\n            \n        def greaterCount(which, val):\n            return sumRange(val+1, n-1, which)\n\n        # Initialize arrays and populate Fenwick tree\n        a1 = [nums[0]]\n        a2 = [nums[1]]\n        update(mp[nums[0]], 0)\n        update(mp[nums[1]], 1)\n\n        # Iterate over the array and update accordingly\n        for i in range(2, n):\n            x = greaterCount(0, mp[nums[i]])\n            y = greaterCount(1, mp[nums[i]])\n                \n            if x > y or (x == y and len(a1) <= len(a2)):\n                a1.append(nums[i])\n                update(mp[nums[i]], 0)\n            elif x < y or (x == y and len(a2) < len(a1)):\n                a2.append(nums[i])\n                update(mp[nums[i]], 1)\n                \n        return a1 + a2\n
['Python3']