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:
greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), append nums[i] to arr1.greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), append nums[i] to arr2.greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), append nums[i] to the array with a lesser number of elements.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 <= 1051 <= nums[i] <= 109Problem Overview: You process an array from left to right and distribute each element into one of two arrays. The decision depends on how many previously placed elements in each array are greater than the current value. If one array has more greater elements, the current number goes there; otherwise tie-breaking rules apply. The challenge is answering "how many elements are greater than x" efficiently while the arrays keep growing.
Approach 1: Sorting + Binary Indexed Tree for Fast Greater Count (O(n log n) time, O(n) space)
This approach compresses the values using sorting so that numbers map to a compact index range. Two Binary Indexed Trees track frequency counts for the two arrays. For every incoming value x, query the Fenwick tree to compute how many elements greater than x already exist in each array using prefix sums. Compare the counts and append the value to the appropriate array, then update that tree. Each query and update costs O(log n), making the full simulation O(n log n). This method is predictable, memory‑efficient, and works well for large value ranges because of coordinate compression.
Approach 2: Balanced Tree with Order Statistics (O(n log n) time, O(n) space)
Instead of coordinate compression, maintain two balanced trees that support order statistics (for example a policy-based tree in C++). Each tree stores inserted values and can return how many elements are strictly greater than a given number in O(log n). While iterating through the array, query both trees, compare the counts, append the element to the chosen array, and insert it into that tree. This removes the need for manual indexing but requires a structure capable of rank queries. Conceptually this behaves like a dynamic sorted container built on a Segment Tree or augmented BST.
Recommended for interviews: The Binary Indexed Tree approach is usually the expected solution. It shows you understand coordinate compression, frequency queries, and efficient counting with Fenwick trees. A brute simulation that scans each array for greater elements would take O(n^2) time and quickly fails on large inputs. Demonstrating the optimized array processing with O(n log n) queries signals strong algorithmic fundamentals.
To efficiently calculate greaterCount, we can use sorted arrays. By keeping the arrays arr1 and arr2 sorted, we can use binary search to quickly find the number of elements greater than the given value, making the decision process faster.
This C solution sorts the arrays arr1 and arr2 each time a new element is added. This allows using binary search to efficiently count the number of elements greater than the current value.
The sorting operation after each insertion gives a complexity of O(n log n), making it efficient given constraints. Insertion itself is O(log n) due to re-sorting using quicksort (for demonstration; a more efficient self-balancing tree or ordered container would be used in practice).
In this approach, instead of using simple sorted arrays, balanced trees like AVL or Red-Black Trees can allow for efficient management of collections. These data structures keep elements sorted and allow quick insertion, deletion, and counting.
This C++ solution uses multiset which provides self-balancing tree mechanisms. This allows for fast operations similar to an ordered set but with duplicates allowed, fitting distribution requirements efficiently.
C++
With balanced tree operations like insertion, deletion, and range count all working in O(log n) time, this method can be optimized further for input sizes up to the upper constraints.
We can use two binary indexed trees tree1 and tree2 to maintain the number of elements in arr1 and arr2 that are less than or equal to a certain number. Each time, we query the number of elements that are less than or equal to the current number in the binary indexed tree, then the number of elements that are greater than the current number is the length of the current array minus the query result. Then we can decide which array to add the current number to based on this difference.
Since the range of numbers given in the problem is very large, we need to discretize these numbers. We can sort these numbers and remove duplicates, then use binary search to find the position of each number in the sorted array.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting for Fast Greater Count | The sorting operation after each insertion gives a complexity of |
| Use of Balanced Trees for Efficient Distribution | With balanced tree operations like insertion, deletion, and range count all working in |
| Discretization + Binary Indexed Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(n) | Small inputs or for understanding the rule before optimizing |
| Sorting + Binary Indexed Tree (Fenwick) | O(n log n) | O(n) | General optimal approach; efficient greater‑count queries with coordinate compression |
| Balanced Tree with Order Statistics | O(n log n) | O(n) | When language libraries provide ordered sets with rank queries |
3072. Distribute Elements Into Two Arrays II | Policy Based Data Structure | PBDS • Aryan Mittal • 6,526 views views
Watch 9 more video solutions →Practice Distribute Elements Into Two Arrays II with our built-in code editor and test cases.
Practice on FleetCode