Problem

You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:

  • The 2D array should contain only the elements of the array nums.
  • Each row in the 2D array contains distinct integers.
  • The number of rows in the 2D array should be minimal.

Return the resulting array. If there are multiple answers, return any of them.

Note that the 2D array can have a different number of elements on each row.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: nums = [1,3,4,1,2,3,1]
Output: [[1,3,4,2],[1,3],[1]]
Explanation: We can create a 2D array that contains the following rows:
- 1,3,4,2
- 1,3
- 1
All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer.
It can be shown that we cannot have less than 3 rows in a valid array.

Example 2

1
2
3

Input: nums = [1,2,3,4]
Output: [[4,3,2,1]]
Explanation: All elements of the array are distinct, so we can keep all of them in the first row of the 2D array.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= nums.length

Solution

Method 1 – Greedy Distribution by Frequency

Intuition

To minimize the number of rows, we should distribute each occurrence of a number into different rows, so that each row contains only distinct numbers. The maximum frequency of any number determines the minimum number of rows needed.

Approach

  1. Count the frequency of each number in nums.
  2. The minimum number of rows needed is the maximum frequency.
  3. Create that many empty rows.
  4. For each number, distribute its occurrences into different rows (one per row, cycling through rows).
  5. Return the resulting 2D array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        int rows = 0;
        for (auto& [k, v] : freq) rows = max(rows, v);
        vector<vector<int>> ans(rows);
        for (auto& [num, cnt] : freq) {
            for (int i = 0; i < cnt; ++i) ans[i].push_back(num);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func FindMatrix(nums []int) [][]int {
    freq := map[int]int{}
    for _, x := range nums { freq[x]++ }
    rows := 0
    for _, v := range freq { if v > rows { rows = v } }
    ans := make([][]int, rows)
    for num, cnt := range freq {
        for i := 0; i < cnt; i++ { ans[i] = append(ans[i], num) }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int rows = 0;
        for (int v : freq.values()) rows = Math.max(rows, v);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < rows; i++) ans.add(new ArrayList<>());
        for (var e : freq.entrySet()) {
            for (int i = 0; i < e.getValue(); i++) ans.get(i).add(e.getKey());
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findMatrix(nums: IntArray): List<List<Int>> {
        val freq = mutableMapOf<Int, Int>()
        for (x in nums) freq[x] = freq.getOrDefault(x, 0) + 1
        val rows = freq.values.maxOrNull() ?: 0
        val ans = List(rows) { mutableListOf<Int>() }
        for ((num, cnt) in freq) {
            for (i in 0 until cnt) ans[i].add(num)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findMatrix(self, nums: list[int]) -> list[list[int]]:
        from collections import Counter
        freq = Counter(nums)
        rows = max(freq.values())
        ans = [[] for _ in range(rows)]
        for num, cnt in freq.items():
            for i in range(cnt):
                ans[i].append(num)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn find_matrix(nums: Vec<i32>) -> Vec<Vec<i32>> {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for x in nums { *freq.entry(x).or_insert(0) += 1; }
        let rows = *freq.values().max().unwrap();
        let mut ans = vec![vec![]; rows];
        for (&num, &cnt) in &freq {
            for i in 0..cnt { ans[i].push(num); }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    findMatrix(nums: number[]): number[][] {
        const freq = new Map<number, number>();
        for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
        const rows = Math.max(...freq.values());
        const ans: number[][] = Array.from({length: rows}, () => []);
        for (const [num, cnt] of freq.entries()) {
            for (let i = 0; i < cnt; i++) ans[i].push(num);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is processed once.
  • 🧺 Space complexity: O(n), for the output 2D array and frequency map.