Convert an Array Into a 2D Array With Conditions — Medium Problem & Solution

Problem statement

Distribute the values of nums into a 2D array so that every row holds distinct integers, every value of nums appears in exactly one row (with multiplicity), and the number of rows is as small as possible.

So the answer is pinned down: put each value in the earliest rows that can still take it, and sort every row in increasing order.

Example 1

Input: nums = [1,3,4,1,2,3,1]
Output: [[1,2,3,4],[1,3],[1]]
Explanation: `1` appears three times, so three rows are needed.

Example 2

Input: nums = [1,2,3,4]
Output: [[1,2,3,4]]
Explanation: All distinct — one row is enough.

Example 3

Input: nums = [2,2,2,2]
Output: [[2],[2],[2],[2]]

Constraints

• 1 <= nums.length <= 200
• 1 <= nums[i] <= nums.length
• Each row is returned in increasing order, and rows are filled from the first one down.

How to solve Convert an Array Into a 2D Array With Conditions

Count each value. A value occurring c times must sit in c different rows, so the answer needs exactly max(count) rows — and placing each value in the first count[v] rows achieves that bound.

Approach

1. Count occurrences of every value.
2. Set rows = max(count).
3. For row r, take every value v with count[v] > r, in increasing order of v.

Why it works

Distinctness within a row means a value occurring c times needs at least c rows, so max(count) is a lower bound. Filling row r with all values whose count exceeds r never repeats a value inside a row and places exactly count[v] copies of each v, so the bound is reached — and since the rule is deterministic, so is the output.

Complexity

• Time — O(n + maxValue)
• Space — O(n)

Pitfalls

• The rows are not equal length; shorter rows come last.
• rows is the largest frequency, not the number of distinct values.
• Sorting each row and filling from the top is what makes the answer unique.

Reference solution

Python

from typing import List

def findMatrix(nums: List[int]) -> List[List[int]]:
    mx = max(nums)
    count = [0] * (mx + 1)
    for v in nums:
        count[v] += 1
    rows = max(count)
    return [[v for v in range(1, mx + 1) if count[v] > r] for r in range(rows)]

JavaScript

var findMatrix = function(nums) {
    var i, v, mx = 0;
    for (i = 0; i < nums.length; i++) if (nums[i] > mx) mx = nums[i];
    var count = [];
    for (v = 0; v <= mx; v++) count.push(0);
    for (i = 0; i < nums.length; i++) count[nums[i]]++;
    var rows = 0;
    for (v = 1; v <= mx; v++) if (count[v] > rows) rows = count[v];
    var out = [];
    for (var r = 0; r < rows; r++) {
        var row = [];
        for (v = 1; v <= mx; v++) if (count[v] > r) row.push(v);
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium