Problem Description

You are given an integer array nums. Your task is to convert this 1D array into a 2D array following these specific rules:

1. All elements must be used: Every element from the original nums array must appear in the 2D array
2. Unique elements per row: Each row in the 2D array can only contain distinct integers (no duplicates within a single row)
3. Minimize rows: The 2D array should have the minimum possible number of rows

The rows in the resulting 2D array can have different lengths - they don't need to be uniform.

For example, if nums = [1,3,4,1,2,3,1], one valid output would be [[1,3,4,2],[1,3],[1]]. Notice how:

• All elements from nums are included
• Each row has no duplicate values
• We use the minimum number of rows needed (3 rows, since element 1 appears 3 times)

The key insight is that the minimum number of rows required equals the maximum frequency of any element in nums. If an element appears k times, it must be distributed across at least k different rows since each row can only contain that element once.

The solution counts the frequency of each element using a Counter, then distributes each element across the appropriate number of rows based on its frequency. For an element x appearing v times, it gets placed into rows 0 through v-1, creating new rows as needed.

Intuition

Let's think about the constraint that each row must contain distinct integers. If we have an element that appears multiple times, say the number 1 appears 3 times in the array, where can we place these three 1s?

Since each row can only contain one instance of 1, we need at least 3 different rows to accommodate all three 1s. This observation leads us to a key realization: the minimum number of rows needed is determined by the element with the highest frequency.

Consider this step-by-step thought process:

1. If every element appeared only once in nums, we could put all elements in a single row
2. If one element appears twice, we need at least 2 rows - one for each occurrence
3. If one element appears k times, we need at least k rows

So the strategy becomes clear:

• Count how many times each element appears
• For each element, distribute its occurrences across different rows
• The element with maximum frequency determines our minimum row count

The distribution pattern is straightforward - for an element x that appears v times:

• Put the first occurrence in row 0
• Put the second occurrence in row 1
• Put the third occurrence in row 2
• Continue until all v occurrences are placed

This greedy approach works because we're not restricted by row lengths. We can keep adding different elements to each row as long as they haven't appeared in that row before. By processing each unique element and distributing its occurrences row by row, we naturally build up our 2D array with the minimum number of rows possible.

Solution Approach

The implementation uses a hash table (Counter) to track element frequencies and builds the 2D array row by row.

Step 1: Count Frequencies

cnt = Counter(nums)

We use Python's Counter to create a frequency map where cnt[x] tells us how many times element x appears in nums.

Step 2: Initialize Result Array

ans = []

Start with an empty list that will hold our rows.

Step 3: Distribute Elements Across Rows

for x, v in cnt.items():
    for i in range(v):
        if len(ans) <= i:
            ans.append([])
        ans[i].append(x)

For each unique element x with frequency v:

• We need to place x into v different rows (rows 0 through v-1)
• For each occurrence i (from 0 to v-1):
  • Check if row i exists: if len(ans) <= i
  • If row i doesn't exist yet, create it: ans.append([])
  • Add element x to row i: ans[i].append(x)

Example Walkthrough: If nums = [1,3,4,1,2,3,1], then cnt = {1:3, 3:2, 4:1, 2:1}

Processing element 1 (frequency 3):

• Add to row 0: ans = [[1]]
• Add to row 1: ans = [[1], [1]]
• Add to row 2: ans = [[1], [1], [1]]

Processing element 3 (frequency 2):

• Add to row 0: ans = [[1,3], [1], [1]]
• Add to row 1: ans = [[1,3], [1,3], [1]]

Processing element 4 (frequency 1):

• Add to row 0: ans = [[1,3,4], [1,3], [1]]

Processing element 2 (frequency 1):

• Add to row 0: ans = [[1,3,4,2], [1,3], [1]]

The algorithm ensures each row contains distinct elements while using the minimum number of rows (equal to the maximum frequency).

Example Walkthrough

Let's walk through a small example with nums = [2,1,2,3,1,3,3].

Step 1: Count frequencies

• Element 1 appears 2 times
• Element 2 appears 2 times
• Element 3 appears 3 times

Since element 3 has the highest frequency (3), we'll need at least 3 rows.

Step 2: Distribute elements row by row

Starting with an empty result: ans = []

Processing element 1 (frequency = 2):

• Place first 1 in row 0: Create row 0 → ans = [[1]]
• Place second 1 in row 1: Create row 1 → ans = [[1], [1]]

Processing element 2 (frequency = 2):

• Place first 2 in row 0: Add to existing row 0 → ans = [[1,2], [1]]
• Place second 2 in row 1: Add to existing row 1 → ans = [[1,2], [1,2]]

Processing element 3 (frequency = 3):

• Place first 3 in row 0: Add to existing row 0 → ans = [[1,2,3], [1,2]]
• Place second 3 in row 1: Add to existing row 1 → ans = [[1,2,3], [1,2,3]]
• Place third 3 in row 2: Create row 2 → ans = [[1,2,3], [1,2,3], [3]]

Final Result: [[1,2,3], [1,2,3], [3]]

Notice how:

• All 7 elements from the original array are included
• Each row contains only distinct values (no duplicates within any row)
• We use exactly 3 rows - the minimum needed since element 3 appears 3 times

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Creating the Counter takes O(n) time as it needs to iterate through all elements in nums
• The nested loops iterate through each element exactly once: for each unique element x with count v, we perform v append operations, and the total number of operations equals n (the total number of elements in the original array)

The space complexity is O(n), where n is the length of the array nums. This is because:

• The Counter object stores at most n key-value pairs (in the worst case where all elements are unique)
• The output list ans stores exactly n elements in total, just reorganized into sublists
• No additional space that scales with input size is used beyond these structures

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Pre-allocate Rows Based on Maximum Frequency

A common mistake is trying to determine the number of rows needed upfront by finding the maximum frequency, then pre-allocating that many empty rows:

Incorrect Approach:

def findMatrix(self, nums: List[int]) -> List[List[int]]:
    frequency_map = Counter(nums)
    max_freq = max(frequency_map.values())
  
    # Pre-allocate all rows
    result = [[] for _ in range(max_freq)]
  
    for number, frequency in frequency_map.items():
        for i in range(frequency):
            result[i].append(number)
  
    return result

Why it fails: If the input is empty (nums = []), max(frequency_map.values()) will raise a ValueError because you cannot take the max of an empty sequence.

Solution: Use the dynamic row creation approach shown in the original solution, or add edge case handling:

if not nums:
    return []
max_freq = max(frequency_map.values()) if frequency_map else 0

2. Modifying the Input Array During Iteration

Some might try to remove elements from nums as they process them:

Incorrect Approach:

def findMatrix(self, nums: List[int]) -> List[List[int]]:
    result = []
    while nums:
        row = []
        seen = set()
        i = 0
        while i < len(nums):
            if nums[i] not in seen:
                seen.add(nums[i])
                row.append(nums[i])
                nums.pop(i)  # Dangerous! Modifying during iteration
            else:
                i += 1
        result.append(row)
    return result

Why it fails: This approach has O(n²) time complexity due to the pop() operations, and can lead to index errors or skipped elements.

Solution: Use a frequency counter approach that doesn't modify the original array, or create a copy if modification is necessary.

3. Using Row Index as Dictionary Key

Trying to use a dictionary with row indices as keys instead of a list:

Incorrect Approach:

def findMatrix(self, nums: List[int]) -> List[List[int]]:
    frequency_map = Counter(nums)
    result_dict = {}
  
    for number, frequency in frequency_map.items():
        for i in range(frequency):
            if i not in result_dict:
                result_dict[i] = []
            result_dict[i].append(number)
  
    return list(result_dict.values())  # Wrong! Dictionary ordering issues

Why it fails: While this might work in Python 3.7+ (where dictionaries maintain insertion order), it's unnecessarily complex and could fail if keys are not sequential starting from 0.

Solution: Use a list directly as shown in the original solution, which naturally maintains order and allows index-based access.