C++ |  Simple Binary Search and Insert at the right location | Brute Force
sharing this solution to help ease my mind after missing a test case due to forgetting to remove a \'cout check\'\n\n# Intuition\n Describe your first thoughts 
sharing this solution to help ease my mind after missing a test case due to forgetting to remove a \'cout check\'\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinarySearch using the `upper_bound` function to find the elements greater than the current = `x` (lets say).\nThen, use `x` to insert the element into the right location in the array, as for the Next Binary Search, you\'ll need the array sorted.\n\n`arr.insert(arr.end() - x, value)`\n\n# To Consider: \nWe need to display the concatenated array in its original order, so for that we can just use 2 extra arrays to keep track of the order, and then concatenate using the insert function\n\n`arr1.insert(arr.end(), arr2.begin(), arr2.end())`\n\n\n# Complexity\n- Time complexity: *O($$n^2$$)*\n\n(at worst case yea, but it passes, leetcode should add some extra testcases)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: *O($$n$$)*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int greaterCount(vector<int>& arr, int val) {\n        return arr.end() - upper_bound(arr.begin(), arr.end(), val);\n    }\n\n    vector<int> resultArray(vector<int>& nums) {\n        int n = nums.size();\n        \n        vector<int> left, right, ll, rr;\n        left.push_back(nums[0]);\n        right.push_back(nums[1]);\n        ll.push_back(nums[0]);\n        rr.push_back(nums[1]);\n        \n        int l = 0, r = 0;\n        \n        for (int i = 2; i < n; i++) {\n            int x = greaterCount(left, nums[i]);\n            int y = greaterCount(right, nums[i]);\n            \n            if (x > y) {\n                \n                left.insert(left.end() - x , nums[i]);\n                ll.push_back(nums[i]);\n                l++;\n            } else if (x < y) {\n                \n                right.insert(right.end() - y, nums[i]);\n                rr.push_back(nums[i]);\n                r++;\n            } else {\n                if (l <= r) {\n                    \n                    left.insert(left.end() - x, nums[i]);\n                    ll.push_back(nums[i]);\n                    l++;\n                } else {\n                    \n                    right.insert(right.end() - y, nums[i]);\n                    rr.push_back(nums[i]);\n                    r++;\n                }\n            }\n        }\n        \n        \n        ll.insert(ll.end(), rr.begin(), rr.end());\n        return ll;\n    }\n};\n\n```
['Binary Search', 'C++']