Loading problem…
You are given a **1-indexed** array of integers `nums` of length `n`. We define a function `greaterCount` 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]` to `arr1`. In the second operation, append `nums[2]` to `arr2`. Afterwards, in the `i`th operation: - If `greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i])`, append `nums[i]` to `arr1`. - If `greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i])`, append `nums[i]` to `arr2`. - If `greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i])`, append `nums[i]` to the array with a **lesser** number of elements. - If there is still a tie, append `nums[i]` to `arr1`. The array `result` is formed by concatenating the arrays `arr1` and `arr2`. Return the integer array `result`.
Example 1
Input: nums = [2,1,3,3]
Output: [2,3,1,3]
Explanation: Start with arr1 = [2] and arr2 = [1]. For the first 3, neither array has a larger element (0 vs 0) and both have the same size, so it goes to arr1 = [2,3]. For the second 3 it is again 0 vs 0, and arr2 is smaller, so arr2 = [1,3]. The result is [2,3,1,3].
Example 2
Input: nums = [5,14,3,1,2]
Output: [5,3,1,2,14]
Explanation: Start with arr1 = [5] and arr2 = [14]. For 3, each array has one larger element, and both have the same size, so 3 goes to arr1. For 1, arr1 has 2 larger elements (5, 3) and arr2 has 1, so 1 goes to arr1. For 2, arr1 again has 2 larger (5, 3) vs 1, so 2 goes to arr1. The result is [5,3,1,2] + [14].
Example 3
Input: nums = [3,3,3,3]
Output: [3,3,3,3]
Explanation: No element is ever strictly greater than 3, so every comparison is a tie and each 3 goes to the shorter array (arr1 when sizes are equal). Both arrays end up as [3,3], and the result is [3,3,3,3].
The only expensive operation is greaterCount(arr, val) = how many elements already in an array exceed val. Maintain a Binary Indexed Tree (Fenwick tree) per array over compressed values; greaterCount is (size) - (count of values <= val), answered in O(log n).
Run checks all cases above. Submit evaluates all test cases.