3072. Distribute Elements Into Two Arrays II LeetCode Solution

In this guide, you will get 3072. Distribute Elements Into Two Arrays II LeetCode Solution with the best time and space complexity. The solution to Distribute Elements Into Two Arrays II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Distribute Elements Into Two Arrays II solution in C++
Distribute Elements Into Two Arrays II solution in Java
Distribute Elements Into Two Arrays II solution in Python
Additional Resources

3072. Distribute Elements Into Two Arrays II LeetCode Solution image

Problem Statement of Distribute Elements Into Two Arrays II

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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

3072. Distribute Elements Into Two Arrays II LeetCode Solution in C++

class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void add(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

 private:
  vector<int> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  vector<int> resultArray(vector<int>& nums) {
    vector<int> arr1;
    vector<int> arr2;
    const unordered_map<int, int> ranks = getRanks(nums);
    FenwickTree tree1(ranks.size());
    FenwickTree tree2(ranks.size());

    add(nums[0], arr1, tree1, ranks);
    add(nums[1], arr2, tree2, ranks);

    for (int i = 2; i < nums.size(); ++i) {
      const int greaterCount1 = arr1.size() - tree1.get(ranks.at(nums[i]));
      const int greaterCount2 = arr2.size() - tree2.get(ranks.at(nums[i]));
      if (greaterCount1 > greaterCount2)
        add(nums[i], arr1, tree1, ranks);
      else if (greaterCount1 < greaterCount2)
        add(nums[i], arr2, tree2, ranks);
      else if (arr1.size() > arr2.size())
        add(nums[i], arr2, tree2, ranks);
      else
        add(nums[i], arr1, tree1, ranks);
    }

    arr1.insert(arr1.end(), arr2.begin(), arr2.end());
    return arr1;
  }

 private:
  unordered_map<int, int> getRanks(const vector<int>& nums) {
    unordered_map<int, int> ranks;
    set<int> sorted(nums.begin(), nums.end());
    int rank = 0;
    for (const int num : sorted)
      ranks[num] = ++rank;
    return ranks;
  }

  void add(int num, vector<int>& arr, FenwickTree& tree,
           const unordered_map<int, int>& ranks) {
    arr.push_back(num);
    tree.add(ranks.at(num), 1);
  };
};
/* code provided by PROGIEZ */

3072. Distribute Elements Into Two Arrays II LeetCode Solution in Java

class FenwickTree {
  public FenwickTree(int n) {
    sums = new int[n + 1];
  }

  public void add(int i, int delta) {
    while (i < sums.length) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

  private int[] sums;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public int[] resultArray(int[] nums) {
    List<Integer> arr1 = new ArrayList<>();
    List<Integer> arr2 = new ArrayList<>();
    Map<Integer, Integer> ranks = getRanks(nums);
    FenwickTree tree1 = new FenwickTree(ranks.size());
    FenwickTree tree2 = new FenwickTree(ranks.size());

    add(nums[0], arr1, tree1, ranks);
    add(nums[1], arr2, tree2, ranks);

    for (int i = 2; i < nums.length; ++i) {
      final int greaterCount1 = arr1.size() - tree1.get(ranks.get(nums[i]));
      final int greaterCount2 = arr2.size() - tree2.get(ranks.get(nums[i]));
      if (greaterCount1 > greaterCount2)
        add(nums[i], arr1, tree1, ranks);
      else if (greaterCount1 < greaterCount2)
        add(nums[i], arr2, tree2, ranks);
      else if (arr1.size() > arr2.size())
        add(nums[i], arr2, tree2, ranks);
      else
        add(nums[i], arr1, tree1, ranks);
    }

    arr1.addAll(arr2);
    return arr1.stream().mapToInt(Integer::intValue).toArray();
  }

  private Map<Integer, Integer> getRanks(int[] nums) {
    Map<Integer, Integer> ranks = new HashMap<>();
    SortedSet<Integer> sorted = new TreeSet<>();
    for (final int num : nums)
      sorted.add(num);
    int rank = 0;
    for (Iterator<Integer> it = sorted.iterator(); it.hasNext();)
      ranks.put(it.next(), ++rank);
    return ranks;
  }

  private void add(int num, List<Integer> arr, FenwickTree tree, Map<Integer, Integer> ranks) {
    arr.add(num);
    tree.add(ranks.get(num), 1);
  };
}
// code provided by PROGIEZ

3072. Distribute Elements Into Two Arrays II LeetCode Solution in Python

class FenwickTree:
  def __init__(self, n: int):
    self.sums = [0] * (n + 1)

  def add(self, i: int, delta: int) -> None:
    while i < len(self.sums):
      self.sums[i] += delta
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    summ = 0
    while i > 0:
      summ += self.sums[i]
      i -= FenwickTree.lowbit(i)
    return summ

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def resultArray(self, nums: list[int]) -> list[int]:
    arr1 = []
    arr2 = []
    ranks = self._getRanks(nums)
    tree1 = FenwickTree(len(ranks))
    tree2 = FenwickTree(len(ranks))

    def add(num: int, arr: list[int], tree: FenwickTree) -> None:
      arr.append(num)
      tree.add(ranks[num], 1)

    add(nums[0], arr1, tree1)
    add(nums[1], arr2, tree2)

    for i in range(2, len(nums)):
      greaterCount1 = len(arr1) - tree1.get(ranks[nums[i]])
      greaterCount2 = len(arr2) - tree2.get(ranks[nums[i]])
      if greaterCount1 > greaterCount2:
        add(nums[i], arr1, tree1)
      elif greaterCount1 < greaterCount2:
        add(nums[i], arr2, tree2)
      elif len(arr1) > len(arr2):
        add(nums[i], arr2, tree2)
      else:
        add(nums[i], arr1, tree1)

    return arr1 + arr2

  def _getRanks(self, nums: list[int]) -> dict[int, int]:
    ranks = collections.Counter()
    rank = 0
    for num in sorted(set(nums)):
      rank += 1
      ranks[num] = rank
    return ranks
 # code by PROGIEZ