C++ Solution, using Binary Search | Easiest and intuitive approach
Intuition\nNeed to search for number of elements greater that current element in optimal time, logn; Best option: use Binary Search for same\n\n# Approach\nNaiv
# Intuition\nNeed to search for number of elements greater that current element in optimal time, logn; Best option: use Binary Search for same\n\n# Approach\nNaive Appproach with added Binary Search\n\n# Complexity\n- Time complexity:\nn(logn)\n\n- Space complexity:\no(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums)\n    {\n        int n=nums.size();\n        vector<int> a;\n        vector<int> b;\n        vector<int> A;\n        vector<int> B;\n        a.push_back(nums[0]);\n        b.push_back(nums[1]);\n        A.push_back(nums[0]);\n        B.push_back(nums[1]);\n        for(int i=2; i<n; i++)\n        {\n            int ita=upper_bound(A.begin(), A.end(), nums[i])-A.begin();\n            int x = A.size()-ita;\n            int itb=upper_bound(B.begin(), B.end(), nums[i])-B.begin();\n            int y = B.size()-itb;\n            if(x>y)\n            {\n                a.push_back(nums[i]);\n                A.insert(A.begin()+ita, nums[i]);\n            }\n            else if(y>x)\n            {\n                b.push_back(nums[i]);\n                B.insert(B.begin()+itb, nums[i]);\n            }\n            else if(a.size()<b.size())\n            {\n                a.push_back(nums[i]);\n                A.insert(A.begin()+ita, nums[i]);\n            }\n            else if(b.size()<a.size())\n            {\n                b.push_back(nums[i]);\n                B.insert(B.begin()+itb, nums[i]);\n            }\n            else\n            {\n                a.push_back(nums[i]);\n                A.insert(A.begin()+ita, nums[i]);\n            }\n        } \n        vector<int> ans;   \n        for(auto it:a)\n        {\n            ans.push_back(it);\n        }\n        for(auto it:b)\n        {\n            ans.push_back(it);\n        }\n        return ans;\n    }\n};\n```
['C++']