Convert an Array Into a 2D Array With Conditions

medium array hash table greedy

Problem

Given an integer array nums, build a 2D array that uses exactly the elements of nums, where every row contains distinct integers and the number of rows is minimal. Return any valid answer. Rows may differ in length.

The key observation: a value that appears k times must land in k different rows, so the minimum number of rows equals the maximum frequency of any value.

Inputnums = [1,3,4,1,2,3,1]

Output[[1,3,4,2],[1,3],[1]]

Value 1 appears 3 times, so at least 3 rows are needed; every row above has distinct integers.

nums (comma-separated)

def findMatrix(nums):
    rows = []           # the 2D result
    seen = {}           # value -> how many rows already hold it
    for v in nums:
        r = seen.get(v, 0)      # next free row for this value
        if r == len(rows):      # no row deep enough yet
            rows.append([])     # open a new row
        rows[r].append(v)       # place v on row r
        seen[v] = r + 1         # this value now occupies one more row
    return rows

function findMatrix(nums) {
  const rows = [];                 // the 2D result
  const seen = new Map();          // value -> how many rows already hold it
  for (const v of nums) {
    const r = seen.get(v) || 0;    // next free row for this value
    if (r === rows.length) {       // no row deep enough yet
      rows.push([]);               // open a new row
    }
    rows[r].push(v);               // place v on row r
    seen.set(v, r + 1);            // this value now occupies one more row
  }
  return rows;
}

List<List<Integer>> findMatrix(int[] nums) {
    List<List<Integer>> rows = new ArrayList<>();
    Map<Integer, Integer> seen = new HashMap<>();
    for (int v : nums) {
        int r = seen.getOrDefault(v, 0);   // next free row for this value
        if (r == rows.size()) {            // no row deep enough yet
            rows.add(new ArrayList<>());   // open a new row
        }
        rows.get(r).add(v);                // place v on row r
        seen.put(v, r + 1);                // value occupies one more row
    }
    return rows;
}

vector<vector<int>> findMatrix(vector<int>& nums) {
    vector<vector<int>> rows;
    unordered_map<int, int> seen;          // value -> rows already holding it
    for (int v : nums) {
        int r = seen[v];                  // next free row (default 0)
        if (r == (int)rows.size()) {      // no row deep enough yet
            rows.push_back({});           // open a new row
        }
        rows[r].push_back(v);             // place v on row r
        seen[v] = r + 1;                  // value occupies one more row
    }
    return rows;
}

Explanation

Because every row must contain distinct integers, two copies of the same value can never share a row. So a value that appears k times forces at least k rows. The most frequent value therefore sets the lower bound on the number of rows, and this greedy placement actually achieves it.

We keep a hash map seen that records, for each value, how many rows already contain a copy of it. When we meet a value v, the count seen[v] is exactly the index of the next row that does not yet hold v — so we drop v there.

If that target row index equals the current number of rows, the row does not exist yet, so we open a fresh empty row first. Then we append v and bump seen[v] by one, ready for the next copy.

This never creates a row with a duplicate (each copy goes one row deeper than the last), and it never wastes rows (a new row is opened only when every existing row already holds the value). Hence the row count equals the maximum frequency — the proven minimum.

Example: for [1,3,4,1,2,3,1] the value 1 appears three times, so it spreads across rows 0, 1, 2, and the answer uses 3 rows: [[1,3,4,2],[1,3],[1]].

Time: O(n) Space: O(n)