Watch 10 video solutions for Convert an Array Into a 2D Array With Conditions, a medium level problem involving Array, Hash Table. This walkthrough by NeetCodeIO has 16,563 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |