Watch 10 video solutions for Distribute Elements Into Two Arrays II, a hard level problem involving Array, Binary Indexed Tree, Segment Tree. This walkthrough by Aryan Mittal has 6,526 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |