# Distribute Elements Into Two Arrays II
**Difficulty:** HARD
[External](https://leetcode.com/problems/distribute-elements-into-two-arrays-ii)
Canonical: https://scaleengineer.com/dsa/problems/distribute-elements-into-two-arrays-ii
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [Autodesk](https://scaleengineer.com/companies/autodesk)
---
## 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 `ith` 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`. 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]
**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].

**Constraints:**

* `3 <= n <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. For each element `nums[i]`, we iterate through the current `arr1` and `arr2` to compute `greaterCount`. This is straightforward to implement but inefficient for large inputs.
**Time:** O(n^2). The main loop runs `n-2` times. In each iteration `i`, calculating `greaterCount` takes `O(size of arr1)` and `O(size of arr2)`, which are both at most `O(i)`. The total time is the sum of `O(i)` for `i` from 1 to `n-1`, which is `O(n^2)`. · **Space:** O(n). We use two lists, `arr1` and `arr2`, to store the `n` elements of the input array.
**Pros:** Simple to understand and implement.; Follows the problem description directly.
**Cons:** Inefficient due to repeated linear scans.; Will result in Time Limit Exceeded (TLE) for large inputs as specified in the constraints (`n <= 10^5`).
### Explanation
We initialize two dynamic arrays, `arr1` and `arr2`.
We place `nums[0]` in `arr1` and `nums[1]` in `arr2` as per the problem statement.
Then, we loop through the rest of the `nums` array from the third element (`i=2`).
In each iteration, we calculate `greaterCount(arr1, nums[i])` and `greaterCount(arr2, nums[i])` by performing a linear scan over `arr1` and `arr2`.
Based on the comparison of these counts and the sizes of `arr1` and `arr2`, we append `nums[i]` to the appropriate array.
The `greaterCount` function simply loops through an array and increments a counter for each element that is strictly greater than the given value.
After processing all elements, we concatenate `arr1` and `arr2` to get the final result.
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private int greaterCount(List<Integer> arr, int val) {
        int count = 0;
        for (int num : arr) {
            if (num > val) {
                count++;
            }
        }
        return count;
    }

    public int[] resultArray(int[] nums) {
        if (nums.length <= 2) {
            return nums;
        }

        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();

        arr1.add(nums[0]);
        arr2.add(nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int val = nums[i];
            int count1 = greaterCount(arr1, val);
            int count2 = greaterCount(arr2, val);

            if (count1 > count2) {
                arr1.add(val);
            } else if (count1 < count2) {
                arr2.add(val);
            } else {
                if (arr1.size() <= arr2.size()) {
                    arr1.add(val);
                } else {
                    arr2.add(val);
                }
            }
        }

        int[] result = new int[nums.length];
        int index = 0;
        for (int num : arr1) {
            result[index++] = num;
        }
        for (int num : arr2) {
            result[index++] = num;
        }
        return result;
    }
}
```
### Algorithm
*   1. Initialize `arr1` with `nums[0]` and `arr2` with `nums[1]`.
*   2. Iterate `i` from 2 to `n-1`:
*   3.   Let `val = nums[i]`.
*   4.   Calculate `count1` by iterating through `arr1` and counting elements `> val`.
*   5.   Calculate `count2` by iterating through `arr2` and counting elements `> val`.
*   6.   If `count1 > count2`, append `val` to `arr1`.
*   7.   Else if `count1 < count2`, append `val` to `arr2`.
*   8.   Else (if counts are equal):
*   9.     If `arr1.size() <= arr2.size()`, append `val` to `arr1`.
*   10.    Else, append `val` to `arr2`.
*   11. Concatenate `arr1` and `arr2` into a result array.

## Optimized Approach using Fenwick Tree and Coordinate Compression
To overcome the `O(n^2)` complexity of the naive approach, we need a faster way to compute `greaterCount`. A Fenwick Tree (or Binary Indexed Tree, BIT) is a data structure that can efficiently find the number of elements in a range and handle point updates. Since the values in `nums` can be large, we first use coordinate compression to map them to a smaller range of indices suitable for the BIT.
**Time:** O(n log n). Coordinate compression takes `O(n log n)` due to sorting. The main loop runs `n` times, and each iteration involves BIT operations (`query` and `update`), which take `O(log m)` time, where `m <= n`. Thus, the loop takes `O(n log n)`. The total complexity is dominated by these parts. · **Space:** O(n). We store `arr1`, `arr2` (`O(n)`), data for coordinate compression (`O(m)`), and two Fenwick Trees (`O(m)`). Since `m <= n`, the total space is `O(n)`.
**Pros:** Highly efficient, with a time complexity suitable for the given constraints.; A standard and powerful technique for problems involving rank-based queries.
**Cons:** More complex to implement than the brute-force approach.; Requires understanding of Fenwick Trees and coordinate compression.
### Explanation
The main bottleneck is the `greaterCount` function. We can optimize this query from `O(n)` to `O(log n)` using a suitable data structure.

**Coordinate Compression**: The values in `nums` can be up to `10^9`, which is too large for direct indexing. We first find all unique values in `nums`, sort them, and create a mapping from each value to its rank (1-indexed position in the sorted unique list). This compresses the value range to `[1, m]`, where `m` is the number of unique elements (`m <= n`).

**Fenwick Tree (BIT)**: We use two Fenwick Trees, `bit1` and `bit2`, corresponding to `arr1` and `arr2`. Each BIT will store the frequencies of the ranks of numbers present in its corresponding array. The size of each BIT will be `m+1`.

This approach reduces the time for each `greaterCount` query to `O(log m)` and each update to `O(log m)`, leading to an overall `O(n log n)` solution.
```java
import java.util.*;

class FenwickTree {
    private int[] bit;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        this.bit = new int[size + 1];
    }

    public void update(int index, int delta) {
        while (index <= size) {
            bit[index] += delta;
            index += index & -index;
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
}

class Solution {
    public int[] resultArray(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return nums;
        }

        // Coordinate Compression
        Set<Integer> uniqueNumsSet = new HashSet<>();
        for (int num : nums) {
            uniqueNumsSet.add(num);
        }
        List<Integer> sortedUniqueNums = new ArrayList<>(uniqueNumsSet);
        Collections.sort(sortedUniqueNums);
        Map<Integer, Integer> valueToRank = new HashMap<>();
        for (int i = 0; i < sortedUniqueNums.size(); i++) {
            valueToRank.put(sortedUniqueNums.get(i), i + 1); // 1-based rank
        }

        int m = sortedUniqueNums.size();
        FenwickTree bit1 = new FenwickTree(m);
        FenwickTree bit2 = new FenwickTree(m);
        
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();

        arr1.add(nums[0]);
        bit1.update(valueToRank.get(nums[0]), 1);
        
        arr2.add(nums[1]);
        bit2.update(valueToRank.get(nums[1]), 1);

        for (int i = 2; i < n; i++) {
            int val = nums[i];
            int rank = valueToRank.get(val);

            int count1 = arr1.size() - bit1.query(rank);
            int count2 = arr2.size() - bit2.query(rank);

            if (count1 > count2) {
                arr1.add(val);
                bit1.update(rank, 1);
            } else if (count1 < count2) {
                arr2.add(val);
                bit2.update(rank, 1);
            } else {
                if (arr1.size() <= arr2.size()) {
                    arr1.add(val);
                    bit1.update(rank, 1);
                } else {
                    arr2.add(val);
                    bit2.update(rank, 1);
                }
            }
        }

        int[] result = new int[n];
        int index = 0;
        for (int num : arr1) {
            result[index++] = num;
        }
        for (int num : arr2) {
            result[index++] = num;
        }
        return result;
    }
}
```
### Algorithm
*   1. Create a sorted list of unique elements from `nums` and a map `valueToRank` to store the 1-based rank of each unique value. Let `m` be the number of unique values.
*   2. Initialize two Fenwick Trees, `bit1` and `bit2`, of size `m`.
*   3. Initialize two lists, `arr1` and `arr2`.
*   4. Add `nums[0]` to `arr1` and update `bit1` at its rank: `bit1.update(valueToRank.get(nums[0]), 1)`.
*   5. Add `nums[1]` to `arr2` and update `bit2` at its rank: `bit2.update(valueToRank.get(nums[1]), 1)`.
*   6. Iterate `i` from 2 to `n-1`:
*   7.   Let `val = nums[i]` and `rank = valueToRank.get(val)`.
*   8.   Calculate `count1 = arr1.size() - bit1.query(rank)`.
*   9.   Calculate `count2 = arr2.size() - bit2.query(rank)`.
*   10.  Apply the distribution rules based on `count1`, `count2`, and list sizes.
*   11.  If `val` is added to `arr1`, call `bit1.update(rank, 1)`.
*   12.  If `val` is added to `arr2`, call `bit2.update(rank, 1)`.
*   13. Concatenate `arr1` and `arr2` to form the final result.

# Solutions
### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; this . c = new int [ n + 1 ]; } public void update ( int x , int delta ) { for (; x <= n ; x += x & - x ) { c [ x ] += delta ; } } public int query ( int x ) { int s = 0 ; for (; x > 0 ; x -= x & - x ) { s += c [ x ]; } return s ; } } class Solution { public int [] resultArray ( int [] nums ) { int [] st = nums . clone (); Arrays . sort ( st ); int n = st . length ; BinaryIndexedTree tree1 = new BinaryIndexedTree ( n + 1 ); BinaryIndexedTree tree2 = new BinaryIndexedTree ( n + 1 ); tree1 . update ( Arrays . binarySearch ( st , nums [ 0 ]) + 1 , 1 ); tree2 . update ( Arrays . binarySearch ( st , nums [ 1 ]) + 1 , 1 ); int [] arr1 = new int [ n ]; int [] arr2 = new int [ n ]; arr1 [ 0 ] = nums [ 0 ]; arr2 [ 0 ] = nums [ 1 ]; int i = 1 , j = 1 ; for ( int k = 2 ; k < n ; ++ k ) { int x = Arrays . binarySearch ( st , nums [ k ]) + 1 ; int a = i - tree1 . query ( x ); int b = j - tree2 . query ( x ); if ( a > b ) { arr1 [ i ++] = nums [ k ]; tree1 . update ( x , 1 ); } else if ( a < b ) { arr2 [ j ++] = nums [ k ]; tree2 . update ( x , 1 ); } else if ( i <= j ) { arr1 [ i ++] = nums [ k ]; tree1 . update ( x , 1 ); } else { arr2 [ j ++] = nums [ k ]; tree2 . update ( x , 1 ); } } for ( int k = 0 ; k < j ; ++ k ) { arr1 [ i ++] = arr2 [ k ]; } return arr1 ; } }
```

### CPP

```cpp
class BinaryIndexedTree { private: int n ; vector < int > c ; public: BinaryIndexedTree ( int n ) : n ( n ) , c ( n + 1 ) {} void update ( int x , int delta ) { for (; x <= n ; x += x & - x ) { c [ x ] += delta ; } } int query ( int x ) { int s = 0 ; for (; x > 0 ; x -= x & - x ) { s += c [ x ]; } return s ; } }; class Solution { public: vector < int > resultArray ( vector < int >& nums ) { vector < int > st = nums ; sort ( st . begin (), st . end ()); int n = st . size (); BinaryIndexedTree tree1 ( n + 1 ); BinaryIndexedTree tree2 ( n + 1 ); tree1 . update ( distance ( st . begin (), lower_bound ( st . begin (), st . end (), nums [ 0 ])) + 1 , 1 ); tree2 . update ( distance ( st . begin (), lower_bound ( st . begin (), st . end (), nums [ 1 ])) + 1 , 1 ); vector < int > arr1 = { nums [ 0 ]}; vector < int > arr2 = { nums [ 1 ]}; for ( int k = 2 ; k < n ; ++ k ) { int x = distance ( st . begin (), lower_bound ( st . begin (), st . end (), nums [ k ])) + 1 ; int a = arr1 . size () - tree1 . query ( x ); int b = arr2 . size () - tree2 . query ( x ); if ( a > b ) { arr1 . push_back ( nums [ k ]); tree1 . update ( x , 1 ); } else if ( a < b ) { arr2 . push_back ( nums [ k ]); tree2 . update ( x , 1 ); } else if ( arr1 . size () <= arr2 . size ()) { arr1 . push_back ( nums [ k ]); tree1 . update ( x , 1 ); } else { arr2 . push_back ( nums [ k ]); tree2 . update ( x , 1 ); } } arr1 . insert ( arr1 . end (), arr2 . begin (), arr2 . end ()); return arr1 ; } };
```

### Python

```python
class BinaryIndexedTree : __slots__ = "n" , "c" def __init__ ( self , n : int ): self . n = n self . c = [ 0 ] * ( n + 1 ) def update ( self , x : int , delta : int ) -> None : while x <= self . n : self . c [ x ] += delta x += x & - x def query ( self , x : int ) -> int : s = 0 while x : s += self . c [ x ] x -= x & - x return s class Solution : def resultArray ( self , nums : List [ int ]) -> List [ int ]: st = sorted ( set ( nums )) m = len ( st ) tree1 = BinaryIndexedTree ( m + 1 ) tree2 = BinaryIndexedTree ( m + 1 ) tree1 . update ( bisect_left ( st , nums [ 0 ]) + 1 , 1 ) tree2 . update ( bisect_left ( st , nums [ 1 ]) + 1 , 1 ) arr1 = [ nums [ 0 ]] arr2 = [ nums [ 1 ]] for x in nums [ 2 :]: i = bisect_left ( st , x ) + 1 a = len ( arr1 ) - tree1 . query ( i ) b = len ( arr2 ) - tree2 . query ( i ) if a > b : arr1 . append ( x ) tree1 . update ( i , 1 ) elif a < b : arr2 . append ( x ) tree2 . update ( i , 1 ) elif len ( arr1 ) <= len ( arr2 ): arr1 . append ( x ) tree1 . update ( i , 1 ) else : arr2 . append ( x ) tree2 . update ( i , 1 ) return arr1 + arr2
```