# Convert an Array Into a 2D Array With Conditions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions)
Canonical: https://scaleengineer.com/dsa/problems/convert-an-array-into-a-2d-array-with-conditions
**Data structures:** Array, Hash Table
**Companies:** [Gojek](https://scaleengineer.com/companies/gojek)
---
## 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.

**Example 1:**

**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:**

**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`

# Approaches
## Iterative Placement with Linear Search
This is a straightforward but inefficient approach that simulates filling the 2D array. For each number from the input, it linearly scans the already created rows to find a suitable place. If a row doesn't contain the number, it's added. If the number is present in all existing rows, a new row is created for it.
**Time:** O(N * k * L), where N is the length of `nums`, k is the number of rows created, and L is the average length of a row. The `list.contains()` method takes O(L) time. In the worst case, both k and L can be proportional to N, leading to a complexity of O(N^3). · **Space:** O(N), where N is the number of elements in `nums`. This space is primarily used to store the output 2D array, which contains all N elements.
**Pros:** The logic is very intuitive and directly follows the problem's description.; It's relatively simple to implement without complex data structures.
**Cons:** Highly inefficient due to nested loops and the linear search (`list.contains()`) within each row.; The time complexity can be as high as O(N^3) in the worst-case scenarios, which may be too slow for larger constraints.
### Explanation
The logic follows a simple simulation. We take numbers one by one from the input `nums` and try to fit them into our resulting 2D array. We start with an empty 2D array. For a number `num`, we check the first row. If `num` is not in the first row, we add it. If it is, we check the second row, and so on. If we go through all existing rows and find that `num` is present in every one of them, we are forced to create a new row and place `num` there. This process guarantees that each row has distinct elements and that we use the minimum number of rows, because a new row is only created out of necessity.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int num : nums) {
            boolean placed = false;
            for (List<Integer> row : result) {
                if (!row.contains(num)) {
                    row.add(num);
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                List<Integer> newRow = new ArrayList<>();
                newRow.add(num);
                result.add(newRow);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an empty list of lists, `result`, to store the 2D array.
*   Iterate through each number `num` in the input array `nums`.
*   For each `num`, set a flag `placed` to `false`.
*   Iterate through each existing `row` in the `result`.
    *   Check if the `row` already contains `num` using a linear scan (`list.contains()`).
    *   If it does not, add `num` to this `row`, set `placed` to `true`, and break the inner loop to move to the next number in `nums`.
*   If, after checking all rows, the `placed` flag is still `false`, it means `num` must go into a new row. Create a new list containing `num` and append it to `result`.
*   After processing all numbers, return `result`.

## Single-Pass with Frequency Counter
This optimal approach solves the problem in a single pass over the input array. The key insight is that the `k`-th occurrence of a number (1-indexed) must be placed in the `(k-1)`-th row (0-indexed). We use a frequency array to track how many times we've seen each number. This count directly gives us the index of the row where the current number should be placed.
**Time:** O(N), where N is the length of `nums`. We iterate through the input array only once, and all operations inside the loop (array access, list access, and adding to a list) take constant or amortized constant time. · **Space:** O(N), where N is the length of `nums`. We use a frequency array of size `N+1` and the `result` list, which stores all N elements.
**Pros:** Extremely efficient with a linear time complexity of O(N).; Solves the problem in a single pass over the input array.; The logic is clean and directly maps the occurrence count to a row index.
**Cons:** Requires extra space for the frequency counter, although this is O(N) which is asymptotically the same as the space required for the output.
### Explanation
This method leverages a frequency counter to determine the correct row for each element in a single pass. The constraints `1 <= nums[i] <= nums.length` allow us to use a simple array as a frequency map for O(1) access.

As we iterate through `nums`, we keep track of how many times we've seen each number. If we encounter a number `x` for the first time, its frequency count is 0, so we place it in row 0. The second time we see `x`, its count is 1, so we place it in row 1, and so on. This ensures that each occurrence of `x` goes into a different row. If we need to place an element in row `k` but `result` only has `k` rows (i.e., indices 0 to `k-1`), we first create row `k` and then add the element. This elegantly constructs the 2D array with the minimum number of rows in one go.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        // The value at freq[num] will tell us which row to place the next occurrence of num.
        int[] freq = new int[nums.length + 1];
        List<List<Integer>> result = new ArrayList<>();

        for (int num : nums) {
            // The row index is the current frequency of the number.
            int rowIndex = freq[num];

            // If this row doesn't exist yet, create it.
            if (rowIndex == result.size()) {
                result.add(new ArrayList<>());
            }

            // Add the number to the determined row.
            result.get(rowIndex).add(num);

            // Increment the frequency for the next time we see this number.
            freq[num]++;
        }

        return result;
    }
}
```
### Algorithm
*   Initialize an empty list of lists, `result`.
*   Create a frequency array, `freq`, of size `nums.length + 1`, initialized to zeros. This array will track the number of times each element has been placed.
*   Iterate through each number `num` in the input array `nums`.
*   The current count `freq[num]` indicates the 0-indexed row where the current `num` should be placed. Let `rowIndex = freq[num]`.
*   If `rowIndex` is equal to the current number of rows in `result` (`result.size()`), it means this row doesn't exist yet. Add a new empty list to `result`.
*   Add `num` to the list at `result.get(rowIndex)`.
*   Increment the count for `num` in the frequency array: `freq[num]++`.
*   After the loop finishes, return `result`.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> findMatrix(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    int n = nums.length;
    int[] cnt = new int[n + 1];
    for (int x : nums) {
      ++cnt[x];
    }
    for (int x = 1; x <= n; ++x) {
      int v = cnt[x];
      for (int j = 0; j < v; ++j) {
        if (ans.size() <= j) {
          ans.add(new ArrayList<>());
        }
        ans.get(j).add(x);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> findMatrix(vector<int> &nums) {
    vector<vector<int>> ans;
    int n = nums.size();
    vector<int> cnt(n + 1);
    for (int &x : nums) {
      ++cnt[x];
    }
    for (int x = 1; x <= n; ++x) {
      int v = cnt[x];
      for (int j = 0; j < v; ++j) {
        if (ans.size() <= j) {
          ans.push_back({});
        }
        ans[j].push_back(x);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]: cnt = Counter(nums) ans = [] for x, v in cnt . items(): for i in range(v): if len(ans) <= i: ans . append([]) ans[i]. append(x) return ans

```