Convert an Array Into a 2D Array With Conditions - Solution & Explanation
Problem Statement
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 <= 2001 <= nums[i] <= nums.length
Approach Overview
Problem 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.
Approach 1: Hash Map with Greedy Distribution
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.
Complexity
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.
Approach 2: Sorting and Placement Strategy
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.
Complexity
Time Complexity: O(n log n), because of sorting.
Space Complexity: O(n), for storing the result array.
Approach 3: Array or Hash Table
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.
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Convert an Array Into a 2D Array With Conditions - Leetcode 2610 - Python • NeetCodeIO • 16,653 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Convert an Array Into a 2D Array With Conditions easy or hard?
Convert an Array Into a 2D Array With Conditions Python/Java solution
How to solve Convert an Array Into a 2D Array With Conditions in O(n)?
What is the best approach for Convert an Array Into a 2D Array With Conditions?
Is Convert an Array Into a 2D Array With Conditions asked at Google/Amazon/Meta?
What data structure is used in Convert an Array Into a 2D Array With Conditions?
What is the time complexity of Convert an Array Into a 2D Array With Conditions?
Ready to solve this problem?
Practice Convert an Array Into a 2D Array With Conditions with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor