Sponsored
Sponsored
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.
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.
1def convertArray(nums):
2 from collections import defaultdict
3 count = defaultdict(int)
4 for num in nums:
5 count[num] += 1
6 max_frequency = max(count.values())
7 result = [[] for _ in range(max_frequency)]
8 index = 0
9 for num, frequency in count.items():
10 for _ in range(frequency):
11 result[index].append(num)
12 index = (index + 1) % max_frequency
13 return result
14
15# Example usage
16nums = [1, 3, 4, 1, 2, 3, 1]
17print(convertArray(nums))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.
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.
Time Complexity: O(n log n), because of sorting.
Space Complexity: O(n), for storing the result array.
1
The Java solution sorts the array and attempts to place each element into existing rows without repetition, adding a new row if necessary to accommodate a unique element.