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.lengthThe 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.
C++
Java
C#
JavaScript
C
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.
C++
Java
C#
JavaScript
C
Time Complexity: O(n log n), because of sorting.
Space Complexity: O(n), for storing the result array.
| 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. |
Convert an Array Into a 2D Array With Conditions - Leetcode 2610 - Python • NeetCodeIO • 16,153 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