Using Sorted Arrays
Intuition\n Describe your first thoughts on how to solve this problem. \nThe given problem involves distributing elements of an array nums into two separate arr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe given problem involves distributing elements of an array nums into two separate arrays arr1 and arr2 based on certain conditions. The conditions are defined by comparing the number of elements in arr1 and arr2 that are strictly greater than the current element being considered from nums.\n\nThe solution uses two additional arrays arr1_sorted and arr2_sorted to store sorted versions of arr1 and arr2, respectively. This sorting helps in efficiently determining the count of elements greater than the current element in each array using binary search.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The greaterCount function calculates the count of elements in a sorted array arr that are strictly greater than a given value val. It does this by using the upper_bound function from the <algorithm> library, which returns an iterator pointing to the first element in the range [arr.begin(), arr.end()) that is greater than val. Subtracting this iterator from arr.end() gives the count of elements greater than val.\n2. The resultArray function initializes four arrays: arr1, arr2, arr1_sorted, and arr2_sorted. It then appends the first two elements of nums into arr1 and arr2 and their sorted versions.\n3. Starting from the third element of nums, the function iterates through the remaining elements. For each element nums[i], it calculates the counts of elements greater than nums[i] in arr1_sorted and arr2_sorted using the greaterCount function.\n4. Based on the counts obtained, the function decides whether to append nums[i] to arr1 or arr2. If the count is greater in arr1_sorted, nums[i] is appended to both arr1_sorted and arr1. If the count is greater in arr2_sorted, nums[i] is appended to both arr2_sorted and arr2. If the counts are equal, the element is appended to the array with fewer elements, or to arr1 if both arrays have the same number of elements.\n5. Finally, the elements of arr2 are appended to arr1, and arr1 is returned as the result.\n\nThis approach ensures that elements are distributed between arr1 and arr2 according to the specified conditions, resulting in the desired result array.\n\n# Code\n```cpp\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        vector<int> arr1_sorted, arr2_sorted, arr1, arr2;\n        arr1.push_back(nums[0]);\n        arr1_sorted.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n        arr2_sorted.push_back(nums[1]);\n        for(int i = 2; i < n; i++) {\n            int x = greaterCount(arr1_sorted, nums[i]);\n            int y = greaterCount(arr2_sorted, nums[i]);\n            if (x > y) {\n                arr1_sorted.insert(arr1_sorted.end() - x , nums[i]);\n                arr1.push_back(nums[i]);\n            } \n            else if (x < y) {\n                arr2_sorted.insert(arr2_sorted.end() - y, nums[i]);\n                arr2.push_back(nums[i]);\n            } \n            else {\n                if(arr1.size() <= arr2.size()) {\n                    arr1_sorted.insert(arr1_sorted.end() - x, nums[i]);\n                    arr1.push_back(nums[i]);\n                } \n                else {\n                    arr2_sorted.insert(arr2_sorted.end() - y, nums[i]);\n                    arr2.push_back(nums[i]);\n                }\n            }\n        }\n        arr1.insert(arr1.end(), arr2.begin(), arr2.end());\n        return arr1;\n    }\n};\n```
['Array', 'Sorting', 'C++']