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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5// A helper struct for mapping size with people's list
6typedef struct {
7 int *people;
8 int size;
9 int capacity;
10} Group;
11
12int** groupThePeople(int* groupSizes, int groupSizesSize, int* returnSize, int** returnColumnSizes) {
13 int** result = malloc(sizeof(int*) * groupSizesSize);
14 *returnColumnSizes = malloc(sizeof(int) * groupSizesSize);
15 int resultIdx = 0;
16
17 Group* groups = malloc(sizeof(Group) * groupSizesSize);
18 for (int i = 0; i < groupSizesSize; ++i) {
19 groups[i].people = malloc(sizeof(int) * groupSizesSize);
20 groups[i].size = 0;
21 groups[i].capacity = 0;
22 }
23
24 for (int i = 0; i < groupSizesSize; ++i) {
25 int size = groupSizes[i];
26 groups[size].people[groups[size].size++] = i;
27 if (groups[size].size == size) {
28 result[resultIdx] = malloc(sizeof(int) * size);
29 for (int j = 0; j < size; ++j) {
30 result[resultIdx][j] = groups[size].people[j];
31 }
32 (*returnColumnSizes)[resultIdx] = size;
33 resultIdx++;
34 groups[size].size = 0;
35 }
36 }
37 free(groups);
38 *returnSize = resultIdx;
39 return result;
40}This C implementation involves using an array of structs to maintain lists of people's indices based on their required group sizes. Similar to hashmap-based implementations, each list is filled until it reaches the correct size, at which point it is added to the result array. Memory management is required for dynamic arrays.
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.
The Python solution manages arrays directly for each group size. As people are processed, they are appended to their respective list. Once full, the list is added to the list of results and reset.