Convert an Array Into a 2D Array With Conditions

How it works

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.

Steps

1. Create a hash map to count how many times each number has been placed (initially 0 for all).
2. Initialize an empty result list.
3. 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.
4. Return the result.

Complexity

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

Things to watch for

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.

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.

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.

from typing import List
from collections import defaultdict

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

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int, int> count;
        vector<vector<int>> res;

        for (int num : nums) {
            int row = count[num];
            if (res.size() == row) {
                res.push_back({});
            }
            res[row].push_back(num);
            count[num]++;
        }

        return res;
    }
};