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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public static List<List<int>> ConvertArray(int[] nums) {
6 Dictionary<int, int> count = new Dictionary<int, int>();
7 foreach (var num in nums) {
8 if (count.ContainsKey(num))
9 count[num]++;
10 else
11 count[num] = 1;
12 }
13 int maxFrequency = 0;
14 foreach (var entry in count) {
15 maxFrequency = Math.Max(maxFrequency, entry.Value);
16 }
17 List<List<int>> result = new List<List<int>>();
18 for (int i = 0; i < maxFrequency; i++) {
19 result.Add(new List<int>());
20 }
21 int index = 0;
22 foreach (var entry in count) {
23 for (int i = 0; i < entry.Value; i++) {
24 result[index].Add(entry.Key);
25 index = (index + 1) % maxFrequency;
26 }
27 }
28 return result;
29 }
30
31 public static void Main() {
32 int[] nums = {1, 3, 4, 1, 2, 3, 1};
33 var result = ConvertArray(nums);
34 foreach (var row in result) {
35 Console.WriteLine(string.Join(" ", row));
36 }
37 }
38}In C#, a Dictionary is used to count the occurrences. The maximum frequency determines the number of rows needed. Each entry is added in a round-robin way to guarantee each row has distinct integers.
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
In C, we begin by sorting the array. We then attempt to insert each element into an existing row without duplication, or create a new row if an element cannot be placed.