Dashboard Problems Interviews Assessments Courses

Greater Count Distribution | CodeGround

Description

Submissions

Greater Count Distribution

Hard

Arrays · Uber

Distribute the values of nums into two arrays, first and second, one value at a time:

nums[0] goes to first and nums[1] goes to second.
For each later value v, let a be the number of elements already in first that are strictly greater than v, and b the same count for second.
If a > b, append v to first.
If a < b, append v to second.
If a == b, append v to whichever array currently has fewer elements; if they have the same length, append to first.

Return first followed by second, concatenated into one list.

Example 1

Input:: nums = [4, 9, 3, 7, 7, 2]
Output:: [4, 3, 9, 7, 7, 2]
Explanation: Start with first = [4], second = [9]. For 3 both counts are 1 and the lengths tie, so it goes to first. Each 7 sees no greater value in first but the 9 in second, so both go to second. For 2, first has 2 greater values and second = [9, 7, 7] has 3, so second again. Result: [4, 3] + [9, 7, 7, 2].

Example 2

Input:: nums = [1, 1, 1, 1]
Output:: [1, 1, 1, 1]
Explanation: Nothing is ever strictly greater, so placement alternates by length: first, then second, giving [1, 1] + [1, 1].

Example 3

Input:: nums = [10, 2, 5, 1, 8]
Output:: [10, 5, 1, 8, 2]
Explanation: 5 sees one greater value in first (10) and none in second, so it joins first. 1 sees two greater values in first vs one in second, so first again. 8 sees one greater (10) vs none, so first, ending with [10, 5, 1, 8] + [2].

Constraints

3 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

</>Code

Output

Run tests to see results.