You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:
nums.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 <= 2001 <= nums[i] <= nums.lengthProblem Overview: Given an integer array nums, build a 2D array where each row contains unique values and every element from nums appears exactly once. The number of rows is not fixed, but duplicates of the same value must appear in different rows.
Approach 1: Hash Map with Greedy Distribution (O(n) time, O(n) space)
This approach tracks how many times each value has appeared while iterating through the array. Use a frequency map (hash table) where freq[x] counts occurrences of x. For every new element, increment its count and place the value in row freq[x] - 1. If that row does not exist yet, create it. The key insight: the maximum frequency of any value determines how many rows are required. Each occurrence of the same value must go into a different row, so mapping occurrence index to row index guarantees uniqueness inside each row. This solution performs constant-time hash lookups and a single pass through the array, making it the optimal approach using hash table operations combined with a greedy placement strategy.
Approach 2: Sorting and Placement Strategy (O(n log n) time, O(n) space)
Another option is to sort the array first, which groups identical values together. After sorting, compute frequencies and determine the maximum frequency to know how many rows are required. Create that many rows and distribute elements so that each duplicate occupies a different row. For example, if a number appears three times, place its occurrences in rows 0, 1, and 2. Sorting simplifies grouping but introduces an O(n log n) cost. This strategy is useful when you already rely on sorted data or want deterministic grouping behavior using basic array operations.
Recommended for interviews: The hash map greedy approach is what most interviewers expect. It shows you recognize that duplicates only conflict within a row and that the number of rows equals the maximum frequency. Implementing the solution with a frequency counter and dynamic row creation demonstrates strong understanding of hash tables and greedy construction. Mentioning the sorting alternative still shows awareness of tradeoffs, but the O(n) greedy solution highlights stronger algorithmic thinking.
The main idea is to utilize a hash map (or dictionary) to count the occurrences of each element in the input array. This helps us determine how many rows we will need based on the maximum frequency of any element.
Then, we iteratively fill the 2D array by distributing each unique element to different rows, ensuring each row contains distinct integers.
The Python solution uses a defaultdict to count occurrences of each element in the array. Then, based on the maximum frequency, it creates the necessary rows in the result array. Using a greedy round-robin method, it fills rows while iterating over each element's frequency.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), because of the storage needed for the count map and result array.
This approach first sorts the array to easily group identical elements. Starting from the least element, it places each new occurrence in different rows to ensure minimal rows while adhering to the distinct integer rule per row.
This Python solution sorts the array and iteratively attempts to place each number in existing rows. If a number can't be placed without repetition, a new row is created.
Time Complexity: O(n log n), because of sorting.
Space Complexity: O(n), for storing the result array.
We first use an array or hash table cnt to count the frequency of each element in the array nums.
Then we iterate through cnt. For each element x, we add it to the 0th row, 1st row, 2nd row, ..., and (cnt[x]-1)th row of the answer list.
Finally, we return the answer list.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Hash Map with Greedy Distribution | Time Complexity: O(n), where n is the length of the array. |
| Sorting and Placement Strategy | Time Complexity: O(n log n), because of sorting. |
| Array or Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map with Greedy Distribution | O(n) | O(n) | General case and interview setting. Fastest solution using frequency counting. |
| Sorting and Placement Strategy | O(n log n) | O(n) | Useful when data is already sorted or when grouping duplicates before placement simplifies implementation. |
Convert an Array Into a 2D Array With Conditions - Leetcode 2610 - Python • NeetCodeIO • 16,563 views views
Watch 9 more video solutions →Practice Convert an Array Into a 2D Array With Conditions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor