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

1. Brute Force

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

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

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)$