LeetCode 2610 - Convert an Array Into a 2D Array With Conditions

LeetCode Problem 2610

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to transform a one-dimensional integer array nums into a two-dimensional array (a list of lists) while satisfying three specific conditions. First, every element from nums must appear in the 2D array exactly as many times as it appears in the original array. Second, each row of the 2D array must contain only distinct integers - no repeated elements within a row. Third, the number of rows in the 2D array should be minimal, meaning we want to organize elements in as few rows as possible while maintaining the distinctness constraint.

The input nums is an array of integers with length between 1 and 200, and each integer is guaranteed to be at least 1 and at most nums.length. The output is a list of lists (2D array) of integers that meets the above conditions. A key point is that the 2D array does not need to be uniform in row length; each row can contain a different number of elements.

Important edge cases include arrays with all unique elements, arrays with all identical elements, and arrays where some elements repeat multiple times. The problem guarantees that the input is non-empty and that integers are within a reasonable range, which makes frequency counting feasible.

Approaches

The brute-force approach is to try to fill rows iteratively by scanning the array and inserting elements into existing rows if they do not already exist there. This approach works because you always maintain the distinctness requirement in each row. However, scanning all rows for each element leads to excessive comparisons, resulting in a potentially quadratic time complexity relative to the number of rows, which is inefficient as the number of repeated elements increases.

The optimal approach uses a frequency map (hash map) to count occurrences of each number in nums. The key observation is that the minimal number of rows is equal to the maximum frequency of any element. This is because no row can contain duplicate elements, so an element that occurs k times must occupy at least k separate rows. Once we know the maximum frequency, we can create that many empty rows initially and distribute the elements one by one into these rows in a round-robin manner, ensuring each row gets only distinct elements. This guarantees minimal rows while satisfying the distinctness constraint.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * r)	O(r)	Scan each element and attempt to insert it into existing rows; r = number of rows
Optimal	O(n)	O(n)	Use frequency map and round-robin distribution; efficient for small n (≤200)

Algorithm Walkthrough

1. Count the frequency of each element in nums using a hash map. This step lets us determine how many times each number must appear in separate rows.
2. Determine the maximum frequency among all numbers. This value is the minimal number of rows required because any number with frequency k cannot appear in fewer than k distinct rows.
3. Initialize a list of empty rows equal to the maximum frequency. Each row will eventually hold unique elements.
4. Iterate over each number and its frequency. For each occurrence of the number, place it into the next available row in round-robin order. For example, if a number appears 3 times, it will be placed in the first three rows respectively. This ensures distinctness within each row.
5. After all elements are distributed, return the list of rows as the resulting 2D array.

Why it works: The algorithm ensures that each row contains distinct integers by distributing repeated elements across different rows. By initializing the number of rows equal to the highest frequency, we guarantee that all occurrences of any element can fit without violating the distinctness condition. This produces a minimal-row solution because any smaller number of rows would be insufficient for the most frequent element.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        freq = Counter(nums)
        max_rows = max(freq.values())
        result = [[] for _ in range(max_rows)]
        
        for num, count in freq.items():
            for i in range(count):
                result[i].append(num)
                
        return result

The Python implementation starts by counting frequencies using Counter, then computes the maximum frequency to determine the number of rows. It initializes result as a list of empty lists and fills them in round-robin order according to each number’s frequency. This directly follows the algorithm walkthrough and ensures correctness and minimal rows.

Go Solution

func findMatrix(nums []int) [][]int {
    freq := make(map[int]int)
    maxRows := 0
    for _, num := range nums {
        freq[num]++
        if freq[num] > maxRows {
            maxRows = freq[num]
        }
    }

    result := make([][]int, maxRows)
    for i := range result {
        result[i] = []int{}
    }

    for num, count := range freq {
        for i := 0; i < count; i++ {
            result[i] = append(result[i], num)
        }
    }

    return result
}

The Go version mirrors the Python logic. A map is used for counting frequencies, maxRows is computed, and slices of slices are initialized for the result. Appending elements to slices in round-robin order guarantees distinctness within rows.

Worked Examples

Example 1: nums = [1,3,4,1,2,3,1]

Step	freq	max_rows	result after placement
Count frequencies	{1:3, 3:2, 4:1, 2:1}	3	[[], [], []]
Place 1 three times	-	-	[[1], [1], [1]]
Place 3 two times	-	-	[[1,3], [1,3], [1]]
Place 4 one time	-	-	[[1,3,4], [1,3], [1]]
Place 2 one time	-	-	[[1,3,4,2], [1,3], [1]]

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

Example 2: nums = [1,2,3,4]

Step	freq	max_rows	result after placement
Count frequencies	{1:1,2:1,3:1,4:1}	1	[[]]
Place each number once	-	-	[[1,2,3,4]]

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Counting frequencies and distributing elements both require linear time relative to the size of nums
Space	O(n)	The frequency map and the result 2D array store at most n elements each

Since the array length is limited to 200, this solution is efficient in practice and scales well within the problem constraints.

Test Cases

# Provided examples
assert Solution().findMatrix([1,3,4,1,2,3,1]) == [[1,3,4,2],[1,3],[1]] or [[1,3,4,2],[1,3],[1]]  # order may vary
assert Solution().findMatrix([1,2,3,4]) == [[1,2,3,4]]

# Single element
assert Solution().findMatrix([5]) == [[5]]

# All identical elements
assert Solution().findMatrix([2,2,2]) == [[2],[2],[2]]

# Two elements, different counts
assert Solution().findMatrix([1,1,2]) == [[1,2],[1]]

# Larger case with multiple repeats
nums = [1,1,2,2,3,3,3]
result = Solution().findMatrix(nums)
for row in result:
    assert len(row) == len(set(row))  # distinct check
flat = [num for row in result for num in row]
assert sorted(flat) == sorted(nums)  # all elements used

Test	Why
[1,3,4,1,2,3,1]	Tests multiple frequencies, ensures minimal rows
[1,2,3,4]	Tests all unique elements, single row output
[5]	Single element edge case
[2,2,2]	All elements identical, number of rows equals frequency
[1,1,2]	Mixed frequencies, checks distribution across rows
[1,1,2,2,3,3,3]	Stress test with multiple repeats and distinctness

Edge Cases

The first edge case is when all elements in nums are unique. A naive implementation might try to create multiple rows unnecessarily, but our approach correctly detects the maximum frequency of 1, generating just a single row.

The second edge case is when all elements are identical. Here, the minimal number of rows equals the length of the array. The algorithm handles this naturally because the maximum frequency calculation accounts for the repetition, and round-robin placement ensures each row gets exactly one occurrence.

The third edge case is when the input array contains a mix of high-frequency and low-frequency elements. This tests whether the round-robin distribution correctly handles different counts and ensures that no row contains