Easy C++ solution using Binary search || Beats 100
Approach\n1. Initialize four vectors a, b, c, and d.\n2. Start iterating through the input array nums from index 2.\n3. For each element nums[i]:\n   - Determin
# Approach\n1. Initialize four vectors `a`, `b`, `c`, and `d`.\n2. Start iterating through the input array `nums` from index 2.\n3. For each element `nums[i]`:\n   - Determine the count of elements greater than `nums[i]` in arrays `a` and `b`. Let\'s call these counts `x` and `y`, respectively.\n   - If `x` is greater than `y`, insert `nums[i]` at the appropriate position in array `a` and add it to array `c`.\n   - If `x` is less than `y`, insert `nums[i]` at the appropriate position in array `b` and add it to array `d`.\n   - If `x` is equal to `y`, insert `nums[i]` in array `b` if the size of array `a` is greater than the size of array `b`; otherwise, insert it in array `a`.\n4. Combine arrays `c` and `d` to form the final result.\n5. Return the result array `c`.\n\n# Complexity\n- Time complexity: \\(O(n \\log n)\\), where \\(n\\) is the size of the input array `nums`. The binary search in the `count` function takes \\(O(\\log n)\\) time, and it is performed for each element in `nums`.\n- Space complexity: \\(O(n)\\) for storing the four arrays `a`, `b`, `c`, and `d`, each with a maximum size of \\(n\\). Therefore, the overall space complexity is \\(O(n)\\).\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int count(vector<int>& a, int k) {\n        int s = 0, e = a.size() - 1;\n        int ans = a.size();\n        while (s <= e) {\n            int mid = (e + s) / 2;\n            if (a[mid] > k) ans = mid;\n            if (a[mid] > k) e = mid - 1;\n            else s = mid + 1;\n        }\n        return ans;\n    }\n    \n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> a, b, c, d;\n        int n = nums.size();\n        a.push_back(nums[0]);\n        b.push_back(nums[1]);\n        c.push_back(nums[0]);\n        d.push_back(nums[1]);\n        for (int i = 2; i < n; i++) {\n            int x = a.size() - count(a, nums[i]); \n            int y = b.size() - count(b, nums[i]);\n            if (x > y) {\n                a.insert(a.end() - x, nums[i]);\n                c.push_back(nums[i]);\n            } else if (x < y) {\n                b.insert(b.end() - y, nums[i]);\n                d.push_back(nums[i]);\n            } else {\n                if (a.size() > b.size()) {\n                    b.insert(b.end() - y, nums[i]);\n                    d.push_back(nums[i]);\n                } else {\n                    a.insert(a.end() - x, nums[i]);\n                    c.push_back(nums[i]);\n                }\n            }\n        }\n        c.insert(c.end(), d.begin(), d.end());\n        return c;\n    }\n};\n```
['C++']