2610. Convert an Array Into a 2D Array With Conditions - Explanation

1. Brute Force

Intuition

We need to distribute numbers into rows such that each row contains only distinct elements. For each number, we find the first row where it doesn't already exist and place it there. If no such row exists, we create a new row. This greedy placement ensures we use the minimum number of rows needed.

Algorithm

Initialize an empty result list to hold the 2D array.
For each number in the input array:
- Start from row 0 and search for a row that doesn't contain this number.
- Check each existing row sequentially until we find one where the number is absent.
- If all existing rows already contain this number, create a new empty row.
- Add the number to the found or newly created row.
Return the result containing all rows.

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        res = []

        for num in nums:
            r = 0
            while r < len(res):
                if num not in res[r]:
                    break
                r += 1
            if r == len(res):
                res.append([])
            res[r].append(num)

        return res

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$ for the output array.

Where $n$ is the size of the array $nums$ and $m$ is the frequency of the most frequent element in the given array.

2. Sorting

Intuition

By sorting the array first, all identical numbers become adjacent. This allows us to process each group of duplicates together. The number of rows needed equals the maximum frequency of any element, and by distributing each group of identical elements across consecutive rows starting from row 0, we ensure each row has distinct values.

Algorithm

Sort the input array.
Initialize an empty result list for the 2D array.
Iterate through the sorted array:
- For each group of identical consecutive numbers, distribute them one per row starting from row 0.
- Create new rows as needed when we encounter more duplicates than existing rows.
- Use two pointers: one to track the start of a group, another to iterate through duplicates.
Move to the next distinct number and repeat.
Return the result.

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []

        i = 0
        while i < len(nums):
            j = i
            r = 0
            while j < len(nums) and nums[i] == nums[j]:
                if r == len(res):
                    res.append([])
                res[r].append(nums[i])
                r += 1
                j += 1
            i = j

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$ for the output array.

3. Frequency Count

Intuition

The frequency of each number tells us exactly which row it should go into. The first occurrence goes to row 0, the second occurrence to row 1, and so on. By tracking how many times we've seen each number, we can directly place it in the correct row without searching. This eliminates the need for both sorting and linear searching.

Algorithm

Create a hash map to count how many times each number has been placed (initially 0 for all).
Initialize an empty result list.
For each number in the array:
- Look up its current count in the hash map. This count indicates which row it belongs to.
- If this row doesn't exist yet, create a new empty row.
- Add the number to the row indicated by its count.
- Increment the count for this number in the hash map.
Return the result.

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        count = defaultdict(int)
        res = []

        for num in nums:
            row = count[num]
            if len(res) == row:
                res.append([])
            res[row].append(num)
            count[num] += 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Confusing Row Index with Frequency Count

A common mistake is using the frequency count incorrectly as the row index. The row where an element should go is determined by how many times it has been placed so far, not its total frequency in the array.

# Wrong - using total frequency
row = total_count[num]

# Correct - using count of placements so far
row = count[num]  # then increment count[num] after placing

Creating Rows Only When Empty

Forgetting to create a new row when needed leads to index out of bounds errors. Before placing an element in a row, check if that row exists.

# Wrong - crashes if row doesn't exist
res[row].append(num)

# Correct - create row if needed
if len(res) == row:
    res.append([])
res[row].append(num)

Using Linear Search for Duplicate Check in Brute Force

In the brute force approach, checking if a number exists in a row using linear search on every insert leads to O(n * m) complexity. While acceptable for the brute force solution, be aware that the frequency count approach achieves O(n) by avoiding these repeated searches entirely.