We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Convert an Array Into a 2D Array With Conditions

Difficulty: Medium

Problem Description

You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:

The 2D array should contain only the elements of the array nums.
Each row in the 2D array contains distinct integers.
The number of rows in the 2D array should be minimal.

Return the resulting array. If there are multiple answers, return any of them.

Note that the 2D array can have a different number of elements on each row.

Key Insights

The problem requires grouping elements into rows while ensuring each row contains distinct values.
The maximum number of rows needed can be determined by the frequency of the most common element in the input array.
A hash table can be used to count the occurrences of each element efficiently.

Space and Time Complexity

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

Solution

To solve this problem, we can use the following approach:

Count the frequency of each integer in the input array using a hash map.
Determine the maximum frequency of any integer, which will dictate the number of rows needed.
Create a list of lists (2D array) to hold the distinct integers.
Distribute the integers into the rows, ensuring that each row contains distinct elements. This can be achieved by iterating over the frequency map and placing integers into the rows in a round-robin fashion.

This approach guarantees that we minimize the number of rows while adhering to the conditions set forth in the problem.

Code Solutions

def convert_to_2d_array(nums):
    from collections import defaultdict
    
    # Step 1: Count the frequency of each number
    frequency = defaultdict(int)
    for num in nums:
        frequency[num] += 1
    
    # Step 2: Determine the maximum frequency
    max_frequency = max(frequency.values())
    
    # Step 3: Create the result 2D array
    result = [[] for _ in range(max_frequency)]
    
    # Step 4: Distribute numbers into the rows
    for num, count in frequency.items():
        for i in range(count):
            result[i].append(num)
    
    return result

← Back to All Questions