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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6vector<vector<int>> convertArray(vector<int>& nums) {
7 unordered_map<int, int> count;
8 for (int num : nums) {
9 count[num]++;
10 }
11 int max_frequency = 0;
12 for (auto& pair : count) {
13 max_frequency = max(max_frequency, pair.second);
14 }
15 vector<vector<int>> result(max_frequency);
16 int index = 0;
17 for (auto& pair : count) {
18 for (int i = 0; i < pair.second; ++i) {
19 result[index].push_back(pair.first);
20 index = (index + 1) % max_frequency;
21 }
22 }
23 return result;
24}
25
26// Example usage
27int main() {
28 vector<int> nums = {1, 3, 4, 1, 2, 3, 1};
29 vector<vector<int>> result = convertArray(nums);
30 for (const auto& row : result) {
31 for (int num : row) {
32 cout << num << " ";
33 }
34 cout << endl;
35 }
36 return 0;
37}The C++ solution uses an unordered_map to count each element's occurrences. It calculates the required number of rows based on the maximum frequency and fills these rows in a round-robin fashion, ensuring each row has distinct elements.
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.
1using System.Collections.Generic;
public class Solution {
public static List<List<int>> ConvertArray(int[] nums) {
Array.Sort(nums);
List<List<int>> result = new List<List<int>>();
foreach (var num in nums) {
bool placed = false;
foreach (var row in result) {
if (!row.Contains(num)) {
row.Add(num);
placed = true;
break;
}
}
if (!placed) {
List<int> newRow = new List<int>();
newRow.Add(num);
result.Add(newRow);
}
}
return result;
}
public static void Main() {
int[] nums = {1, 3, 4, 1, 2, 3, 1};
var result = ConvertArray(nums);
foreach (var row in result) {
Console.WriteLine(string.Join(" ", row));
}
}
}The C# implementation sorts the array, tries to place each integer in existing non-repetitive rows, creating new ones when required, thus ensuring minimum necessary rows.