Convert an Array Into a 2D Array With Conditions

Medium
910.

Convert an Array Into a 2D Array With Conditions

Convert an Array Into a 2D Array With Conditions is a medium coding problem on arrays, hash table and matrix, asked in Amazon, Microsoft and TCS interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findMatrix = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Convert an Array Into a 2D Array With Conditions — Solution

Convert an Array Into a 2D Array With Conditions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Convert an Array Into a 2D Array With Conditions is a medium coding problem on arrays, hash table and matrix, asked in Amazon, Microsoft and TCS interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Matrix
  • Asked at: Amazon, Microsoft, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Convert an Array Into a 2D Array With Conditions

  1. Hint 1

    How many rows does a value that occurs c times force?

  2. Hint 2

    The row count is the largest frequency in nums.

  3. Hint 3

    A value with frequency c belongs in rows 0 … c - 1.

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

Java

public static int[][] findMatrix(int[] nums) {
    int mx = 0;
    for (int v : nums) mx = Math.max(mx, v);
    int[] count = new int[mx + 1];
    for (int v : nums) count[v]++;
    int rows = 0;
    for (int v = 1; v <= mx; v++) rows = Math.max(rows, count[v]);
    List<int[]> out = new ArrayList<>();
    for (int r = 0; r < rows; r++) {
        List<Integer> row = new ArrayList<>();
        for (int v = 1; v <= mx; v++) if (count[v] > r) row.add(v);
        int[] arr = new int[row.size()];
        for (int k = 0; k < arr.length; k++) arr[k] = row.get(k);
        out.add(arr);
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> findMatrix(vector<int>& nums) {
    int mx = 0;
    for (int v : nums) mx = max(mx, v);
    vector<int> count(mx + 1, 0);
    for (int v : nums) count[v]++;
    int rows = 0;
    for (int v = 1; v <= mx; v++) rows = max(rows, count[v]);
    vector<vector<int>> out;
    for (int r = 0; r < rows; r++) {
        vector<int> row;
        for (int v = 1; v <= mx; v++) if (count[v] > r) row.push_back(v);
        out.push_back(row);
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets