Distribute Elements Into Two Arrays II
You are given a 1-indexed array of integers nums of length n.
Define a function greaterCount(arr, val) such that greaterCount(arr, val) returns the number of elements in arr that are strictly greater than val.
You need to distribute all the elements of nums between two arrays arr1 and arr2 using n operations:
- In the first operation, append
nums[1]toarr1. - In the second operation, append
nums[2]toarr2. - Afterwards, in the
i^thoperation: - If
greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), appendnums[i]toarr1. - If
greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), appendnums[i]toarr2. - If
greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), appendnums[i]to the array with a lesser number of elements. - If there is still a tie, append
nums[i]toarr1.
The array result is formed by concatenating the arrays arr1 and arr2. For example, if arr1 == [1,2,3] and arr2 == [4,5,6], then result = [1,2,3,4,5,6].
Return the integer array result.
Example 1
Input
nums = [2,1,3,3]Output
[2,3,1,3]After the operations, arr1 = [2,3] and arr2 = [1,3], so concatenating them gives [2,3,1,3].
Example 2
Input
nums = [5,14,3,1,2]Output
[5,3,1,2,14]After the operations, arr1 = [5,3,1,2] and arr2 = [14], so concatenating them gives [5,3,1,2,14].
Constraints
- 3 <= n <= 10^5
- 1 <= nums[i] <= 10^9