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] <= 109The key challenge in #3072 Distribute Elements Into Two Arrays II is efficiently deciding where to place each element while maintaining counts of greater elements in two dynamically growing arrays. A naive simulation would require repeatedly scanning arrays, which leads to O(n^2) time and becomes infeasible for large inputs.
An optimized strategy uses advanced data structures such as a Binary Indexed Tree (Fenwick Tree) or a Segment Tree. First, apply coordinate compression to map values into a manageable index range. As elements are processed, maintain frequency structures for both arrays. For each new element, query how many previously inserted values are greater in each structure, which determines the array where the element should be placed.
These trees allow efficient prefix or range queries and updates in O(log n) time. By combining coordinate compression with Fenwick/Segment Tree queries, the algorithm simulates the distribution process efficiently while maintaining accurate counts.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Indexed Tree with Coordinate Compression | O(n log n) | O(n) |
| Segment Tree Based Simulation | O(n log n) | O(n) |
| Naive Simulation | O(n^2) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
We need a data structure that counts the number of integers greater than a given value <code>x</code> and supports insertion.
Use Segment Tree or Binary Indexed Tree by compressing the numbers to the range <code>[1,n]</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Coordinate compression maps potentially large values into a smaller continuous range of indices. This makes it feasible to use Fenwick Trees or Segment Trees efficiently without allocating excessive memory.
Hard problems involving Fenwick Trees, Segment Trees, and advanced simulation are common in top tech company interviews. While this exact problem may not always appear, similar patterns that require efficient counting and dynamic data structures are frequently tested.
A Binary Indexed Tree (Fenwick Tree) is commonly used because it supports efficient prefix queries and updates in logarithmic time. A Segment Tree can also be used for the same purpose, especially when implementing range queries and dynamic frequency tracking.
The optimal approach uses coordinate compression along with a Binary Indexed Tree or Segment Tree to track counts of elements efficiently. This allows quick queries for how many previous elements are greater than the current value in each array, reducing the overall complexity to O(n log n).