Binary Indexed Tree | Coordinate compression | C++ fast and easy solution
Intuition\nThe crux of this question is to figure out how many elements are greater than the current number. You can use some non-standard libraries to do so, b
# Intuition\nThe crux of this question is to figure out `how many elements are greater than the current number`. You can use some non-standard libraries to do so, but I would encourage not doing so, since these aren\'t allowed in an interview.\nI have used a BIT (binary indexed tree) or a Fenwick tree to do a RangeSumQuery and find out number of elements greater than `nums[i]` at the i<sup>th</sup> iteration.\n\n# Approach\nWhat does the BIT store:\nThe BIT is for a range of [0,10<sup>5</sup>], which stores a boolen value whether this element is present of not. Thus doing a range sum over `[elem+1,LIM]` (LIM is the size of the array), would return the number of elements greater than `elem`.\n\nAn outline of the complete algorithm:\n- The range of nums[i] is [0,10<sup>9</sup>], thus we need to do coordinate compression to bring this in the range [0,10<sup>5</sup>].\n- We create 2 FenwickTrees for this range [0,10<sup>5</sup>], one for each of arr1 and arr2.\n- At each iteration we find the no. of elements greater than `nums[i]` in both the BITs. \n- Rest of the logic is self explanatory, as we proceed in the same fashion as outlined in the problem.\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n) for fenwick tree.\n\n# Code\n```\nclass FenwickTree{\n    private:\n    vector<int>ft;\n    int LSOne(int n){return n&(-n);}\n    int getPrefixSum(int ind){\n        int ans=0;\n        for(;ind>0;ind-=LSOne(ind)) ans+= ft[ind];\n        return ans;\n    }\n    public:\n    FenwickTree(int n){\n        ft.assign(n+1,0);\n    }\n    void update(int ind, int val){\n        while(ind < ft.size()){\n            ft[ind] += val;\n            ind += LSOne(ind);\n        }\n    }\n    int getRangeSum(int low, int high){\n        return getPrefixSum(high) - (low>1 ? getPrefixSum(low-1):0);\n    }\n};\nclass CoordinateCompression{\n    public:\n    static map<int,int> compress(vector<int> &v){\n        map<int,int> id;\n        map<int,int> reverseId;\n        for(int elem:v){\n            id[elem] = 0;\n        }\n        int c = 1;\n        for(auto elem:id){\n            id[elem.first] = c;\n            reverseId[c] = elem.first;\n            c++;\n        }\n        for(int i=0;i<v.size();i++){\n            v[i] = id[v[i]];\n        }\n        return reverseId;\n    }\n    static void decompress(vector<int> &v, map<int,int>& id){\n        for(int i=0;i<v.size();i++){\n            v[i] = id[v[i]];\n        }\n    }\n};\nclass Solution {\npublic:\n    int greater(FenwickTree& ft, int num, int LIM){\n        if(num == LIM) return 0;\n        return ft.getRangeSum(num+1, LIM);\n    }\n    vector<int> resultArray(vector<int>& nums) {\n        map<int,int> ids = CoordinateCompression::compress(nums);\n        int LIM = *max_element(nums.begin(),nums.end());\n        for(auto elem:nums)cout<<elem<<" ";\n        cout<<endl;\n        FenwickTree ft1(LIM), ft2(LIM);\n        vector<int> v1, v2;\n        v1.push_back(nums[0]);\n        ft1.update(nums[0],1);\n        v2.push_back(nums[1]);\n        ft2.update(nums[1],1);\n        for(int i=2;i<nums.size();i++){\n            int g1 = greater(ft1, nums[i], LIM);\n            int g2 = greater(ft2, nums[i], LIM);\n            if(g1 > g2){\n                v1.push_back(nums[i]);\n                ft1.update(nums[i],1);\n            }\n            else if(g1 < g2){\n                v2.push_back(nums[i]);\n                ft2.update(nums[i],1);\n            }\n            else if(g1 == g2){\n                if(v1.size() < v2.size())\n                    v1.push_back(nums[i]),ft1.update(nums[i],1);\n                else if(v1.size() > v2.size())\n                    v2.push_back(nums[i]),ft2.update(nums[i],1);\n                else\n                    v1.push_back(nums[i]),ft1.update(nums[i],1);\n            }\n        }\n        for(auto elem:v2){\n            v1.push_back(elem);\n        }\n        CoordinateCompression::decompress(v1, ids);\n        return v1;\n    }\n};\n```
['Bit Manipulation', 'Binary Indexed Tree', 'C++']