Distribute Elements Into Two Arrays II

Distribute Elements Into Two Arrays II

What is this problem about?

This is the "Hard" version of the distribution problem. In Distribute Elements Into Two Arrays II, the rule for placement changes: you compare the number of elements already in the array that are strictly greater than the current element. If arr1 has more such elements, the new element goes to arr1. If arr2 has more, it goes to arr2. If they are equal, it goes to the array with fewer elements. If still equal, it goes to arr1.

Why is this asked in interviews?

Autodesk uses this to test your ability to optimize "Greater Than" queries in a data stream. A naive $O(N)$ search for every new element would result in $O(N^2)$ overall, which is too slow for large inputs ($10^5$). It evaluation your knowledge of Binary Indexed Trees (BIT) or Segment Trees to perform point updates and range queries in $O(\log N)$ time.

Algorithmic pattern used

This problem uses Coordinate Compression and a Binary Indexed Tree (BIT).

1. Since the numbers can be large but we only care about their relative order, compress all unique numbers in nums to the range $[1, UniqueCount]$.
2. Maintain two BITs, one for each array, to track the frequencies of the compressed values.
3. To find "elements greater than $X$," you query the BIT for the sum of frequencies in the range $[compressed(X)+1, UniqueCount]$.
4. This reduces each decision to $O(\log N)$.

Example explanation

nums = [2, 1, 3, 3], arr1=[2], arr2=[1]. Next is 3.

1. arr1 has 0 elements $> 3$.
2. arr2 has 0 elements $> 3$.
3. Equal counts! arr1 has 1 element, arr2 has 1 element.
4. Equal size! Go to arr1. arr1 = [2, 3]. Next is 3.
5. arr1 has 0 elements $> 3$ (it has 2, 3... neither is $> 3$).
6. ... continue the logic.

Common mistakes candidates make

• Complexity: Trying to use a standard list and count function, which is $O(N^2)$.
• Coordinate Compression: Failing to handle large values by mapping them to indices, which is necessary for BIT implementation.
• Off-by-one: Incorrectly defining the range for "strictly greater" in the BIT query.

Interview preparation tip

When you see "count elements greater than X" in a dynamic array, think Binary Indexed Tree or Segment Tree. These are the standard tools for $O(\log N)$ order statistics. Practice coordinate compression as it is a prerequisite for using these structures with large input values.