Sponsored
Sponsored
This approach involves using a hashmap (or dictionary) to keep track of members that belong to groups of the same size. You iterate over the groupSizes array, and for each person, add their ID to a list associated with their required group size in the hashmap. Once a list reaches the intended group size, you add it to the result and reset the list for that group size.
The time complexity is O(n), where n is the number of people, because each person is processed exactly once. The space complexity is also O(n), because we store the people in an intermediate dictionary before creating the result.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<IList<int>> GroupThePeople(int[] groupSizes) {
6 var sizeToPeople = new Dictionary<int, List<int>>();
7 var result = new List<IList<int>>();
8 for (int i = 0; i < groupSizes.Length; i++) {
9 int size = groupSizes[i];
10 if (!sizeToPeople.ContainsKey(size)) {
11 sizeToPeople[size] = new List<int>();
12 }
13 sizeToPeople[size].Add(i);
14 if (sizeToPeople[size].Count == size) {
15 result.Add(new List<int>(sizeToPeople[size]));
16 sizeToPeople[size].Clear();
17 }
18 }
19 return result;
20 }
21}This C# implementation utilizes a Dictionary to collect groups of people with the same size requirement. After appending each person, they are added to the result list if their group size is complete, and the temporary list is cleared for reuse.
This approach uses direct index management without using a hashmap, iterating through the list and directly placing IDs into result groups once a correct-sized group is filled, simplifying the storage by maintaining an array or linked list for each group size.
The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements.
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> GroupThePeople(int[] groupSizes) {
var result = new List<IList<int>>();
List<int>[] groups = new List<int>[groupSizes.Length + 1];
for (int i = 0; i < groupSizes.Length; i++) {
int size = groupSizes[i];
if (groups[size] == null) groups[size] = new List<int>();
groups[size].Add(i);
if (groups[size].Count == size) {
result.Add(new List<int>(groups[size]));
groups[size].Clear();
}
}
return result;
}
}C# adapts the approach using an array of typed generic lists directly tracking group memberships by size, efficiently managing and clearing lists when full.