LeetCode 3072: Distribute Elements Into Two Arrays II Solution

Master LeetCode problem 3072 (Distribute Elements Into Two Arrays II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3072. Distribute Elements Into Two Arrays II

Hard

Array Binary Indexed Tree Segment Tree Simulation

Problem Explanation

Explanation

To solve this problem, we can iterate through the given array nums and distribute the elements into two arrays arr1 and arr2 based on the conditions specified. We can maintain a count of elements greater than the current element in both arrays and append the current element to the array with fewer elements greater than it. In case of a tie, we append the current element to arr1.

Algorithm

Initialize two arrays arr1 and arr2.
Iterate through the elements of nums.
For each element num[i], count the number of elements greater than num[i] in both arr1 and arr2.
Append num[i] to the array with fewer elements greater than it.
If the counts are equal, append to arr1.
Return the concatenated array result of arr1 and arr2.

Time Complexity

The time complexity of this algorithm is O(n log n), where n is the number of elements in the given array nums.

Space Complexity

The space complexity of this algorithm is O(n), where n is the number of elements in the given array nums.

Solution Code

class Solution {
    public int[] distributeElements(int[] nums) {
        int n = nums.length;
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int count1 = 0, count2 = 0;
            for (int num : arr1) {
                if (num > nums[i]) {
                    count1++;
                }
            }
            for (int num : arr2) {
                if (num > nums[i]) {
                    count2++;
                }
            }
            
            if (count1 > count2) {
                arr2.add(nums[i]);
            } else if (count1 < count2) {
                arr1.add(nums[i]);
            } else {
                arr1.add(nums[i]);
            }
        }
        
        int[] result = new int[n];
        int idx = 0;
        for (int num : arr1) {
            result[idx++] = num;
        }
        for (int num : arr2) {
            result[idx++] = num;
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3072 (Distribute Elements Into Two Arrays II)?

This page provides optimized solutions for LeetCode problem 3072 (Distribute Elements Into Two Arrays II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3072 (Distribute Elements Into Two Arrays II)?

The time complexity for LeetCode 3072 (Distribute Elements Into Two Arrays II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3072 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3072 in Java, C++, or Python.

Back to LeetCode Solutions