Problem Description
You are given a 1-indexed array of integers nums of length n. You need to distribute all the elements of nums between two arrays arr1 and arr2 using n operations according to specific rules related to the counts of greater elements in each array.
Key Insights
- The first element always goes to arr1 and the second to arr2.
- For each subsequent element, it is appended to either arr1 or arr2 based on the count of elements greater than the current element in both arrays.
- Ties are resolved by choosing the array with fewer elements or defaulting to arr1 if both arrays have equal lengths.
Space and Time Complexity
Time Complexity: O(n^2) in the worst case (due to counting greater elements repeatedly). Space Complexity: O(n) for storing the two arrays.
Solution
To solve this problem, we maintain two arrays, arr1 and arr2, and keep track of the number of elements in each. For each element in the input array, we calculate the number of elements in arr1 and arr2 that are greater than the current element using a helper function greaterCount. We append the current element to the appropriate array based on the defined rules. This involves a simulation approach where we iteratively process each element and update the arrays accordingly.