#3072
Distribute Elements Into Two Arrays II
international master · 1975 · lc hard +32 · failed · 30.4% accepted · 157 likes · top 8%
Description
Given a 1-indexed integer array nums, let greaterCount(arr, val) be the number of elements in arr strictly greater than val. Distribute elements into arr1 and arr2: place nums[1] in arr1 and nums[2] in arr2. For each subsequent nums[i]:
- Append to arr1 if greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]).
- Append to arr2 if greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]).
- If counts are equal, append to the shorter array; if still tied, append to arr1.
Return the concatenation arr1 + arr2.
Example 1:
Input: nums = [2,1,3,3]
Output: [2,3,1,3]
Explanation: After the first 2 operations, arr1 = [2] and arr2 = [1].
In the 3rd operation, the number of elements greater than 3 is zero in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1.
In the 4th operation, the number of elements greater than 3 is zero in both arrays. As the length of arr2 is lesser, hence, append nums[4] to arr2.
After 4 operations, arr1 = [2,3] and arr2 = [1,3].
Hence, the array result formed by concatenation is [2,3,1,3].
Example 2:
Input: nums = [5,14,3,1,2]
Output: [5,3,1,2,14]
Explanation: After the first 2 operations, arr1 = [5] and arr2 = [14].
In the 3rd operation, the number of elements greater than 3 is one in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1.
In the 4th operation, the number of elements greater than 1 is greater in arr1 than arr2 (2 > 1). Hence, append nums[4] to arr1.
In the 5th operation, the number of elements greater than 2 is greater in arr1 than arr2 (2 > 1). Hence, append nums[5] to arr1.
After 5 operations, arr1 = [5,3,1,2] and arr2 = [14].
Hence, the array result formed by concatenation is [5,3,1,2,14].
Example 3:
Input: nums = [3,3,3,3]
Output: [3,3,3,3]
Explanation: At the end of 4 operations, arr1 = [3,3] and arr2 = [3,3].
Hence, the array result formed by concatenation is [3,3,3,3].
Code
1
2
3