Convert an Array Into a 2D Array With Conditions

Med

#2390Time: 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.1 company

Data structures

Array Hash Table

Companies

Gojek

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<List<Integer>> findMatrix(int[] nums) {6        List<List<Integer>> result = new ArrayList<>();7        for (int num : nums) {8            boolean placed = false;9            for (List<Integer> row : result) {10                if (!row.contains(num)) {11                    row.add(num);12                    placed = true;13                    break;14                }15            }16            if (!placed) {17                List<Integer> newRow = new ArrayList<>();18                newRow.add(num);19                result.add(newRow);20            }21        }22        return result;23    }24}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<List<Integer>> findMatrix(int[] nums) {6        // The value at freq[num] will tell us which row to place the next occurrence of num.7        int[] freq = new int[nums.length + 1];8        List<List<Integer>> result = new ArrayList<>();9 10        for (int num : nums) {11            // The row index is the current frequency of the number.12            int rowIndex = freq[num];13 14            // If this row doesn't exist yet, create it.15            if (rowIndex == result.size()) {16                result.add(new ArrayList<>());17            }18 19            // Add the number to the determined row.20            result.get(rowIndex).add(num);21 22            // Increment the frequency for the next time we see this number.23            freq[num]++;24        }25 26        return result;27    }28}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  List<List<Integer>> findMatrix(int[] nums) {4    List<List<Integer>> ans = new ArrayList<>();5    int n = nums.length;6    int[] cnt = new int[n + 1];7    for (int x : nums) {8      ++cnt[x];9    }10    for (int x = 1; x <= n; ++x) {11      int v = cnt[x];12      for (int j = 0; j < v; ++j) {13        if (ans.size() <= j) {14          ans.add(new ArrayList<>());15        }16        ans.get(j).add(x);17      }18    }19    return ans;20  }21}

1class Solution {2public:3  vector<vector<int>> findMatrix(vector<int> &nums) {4    vector<vector<int>> ans;5    int n = nums.size();6    vector<int> cnt(n + 1);7    for (int &x : nums) {8      ++cnt[x];9    }10    for (int x = 1; x <= n; ++x) {11      int v = cnt[x];12      for (int j = 0; j < v; ++j) {13        if (ans.size() <= j) {14          ans.push_back({});15        }16        ans[j].push_back(x);17      }18    }19    return ans;20  }21};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem