Skip to main content
Talentd

Distribute Elements Into Two Arrays II - Solution & Explanation

HardArrayBinary Indexed TreeSegment TreeSimulation18 min readAsked at: Capital One, Autodesk
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Sorting for Fast Greater Count

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.

Sorting for Fast Greater Count

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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).

Try this approach in the editor →

Approach 2: Use of Balanced Trees for Efficient Distribution

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.

Use of Balanced Trees for Efficient Distribution

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.

Code

C++

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Discretization + Binary Indexed Tree

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting for Fast Greater Count

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).

Use of Balanced Trees for Efficient Distribution

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.

Discretization + Binary Indexed Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(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 StatisticsO(n log n)O(n)When language libraries provide ordered sets with rank queries

Video Solution

3072. Distribute Elements Into Two Arrays II | Policy Based Data Structure | PBDS • Aryan Mittal • 6,775 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Distribute Elements Into Two Arrays II easy or hard?
Distribute Elements Into Two Arrays II is rated Hard on LeetCode. The difficulty comes from recognizing that naive simulation is too slow and that you must maintain dynamic counts of greater elements efficiently using advanced data structures such as Fenwick Trees or segment trees.
How to solve Distribute Elements Into Two Arrays II in O(n)?
A strict O(n) solution is generally not feasible because the algorithm must repeatedly compute ordered statistics (count of elements greater than a value). These operations require a data structure such as a Fenwick Tree, Segment Tree, or balanced BST, each taking O(log n) time. The best achievable complexity in practice is O(n log n).
What is the best approach for Distribute Elements Into Two Arrays II?
The most practical solution uses coordinate compression with a Binary Indexed Tree (Fenwick Tree). Two Fenwick trees track frequencies of elements inserted into each array. For every new value, you query how many existing elements are greater than it and decide where it should go. This produces an O(n log n) time solution with O(n) space.
Is Distribute Elements Into Two Arrays II asked at Google/Amazon/Meta?
Problems involving order statistics, Fenwick trees, and dynamic frequency counting appear frequently in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the underlying technique of using Binary Indexed Trees or segment trees for efficient counting is commonly tested.
What data structure is used in Distribute Elements Into Two Arrays II?
The core data structures are Binary Indexed Trees (Fenwick Trees) or balanced binary search trees with order statistics. These structures allow efficient queries for how many elements are greater than a given value while supporting dynamic insertions.
What is the time complexity of Distribute Elements Into Two Arrays II?
The optimized solution runs in O(n log n) time. Each element requires a logarithmic query and update on a Binary Indexed Tree or balanced tree to count how many elements are greater than the current value. Space complexity is O(n) to store the arrays and frequency structures.
Distribute Elements Into Two Arrays II Python or Java solution approach?
In Python or Java, the common approach uses coordinate compression combined with a Fenwick Tree implementation. Each number is mapped to a compressed index, then prefix sums determine how many larger elements exist. Insertions and queries both run in O(log n), giving an overall O(n log n) algorithm.

Ready to solve this problem?

Practice Distribute Elements Into Two Arrays II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Array Into Equal Pairs

Next

Split Array Largest Sum