Group the People Given the Group Size They Belong To - Problem

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in.

For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Input & Output

Example 1 — Mixed Group Sizes

$ Input: groupSizes = [3,3,3,3,3,1,3]

› Output: [[5],[0,1,2],[3,4,6]]

💡 Note: Person 5 wants group size 1, so gets their own group. People 0,1,2 all want size 3, so form one group. People 3,4,6 also want size 3, forming another group.

Example 2 — All Same Size

$ Input: groupSizes = [2,1,3,3,3,2]

› Output: [[1],[0,5],[2,3,4]]

💡 Note: Person 1 wants size 1. People 0,5 want size 2. People 2,3,4 want size 3. Each gets grouped with others of same preference.

Example 3 — Edge Case Small

$ Input: groupSizes = [1]

› Output: [[0]]

💡 Note: Single person wants group size 1, so forms their own group.

Constraints

groupSizes.length == n
1 ≤ n ≤ 500
1 ≤ groupSizes[i] ≤ n

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is that people with the same group size requirement can be grouped together greedily. Best approach is Hash Map Grouping - collect people by their required group size and form complete groups immediately. Time: O(n), Space: O(n)

Common Approaches

✓ Optimized

⏱️ Time: N/A Space: N/A

Brute Force - Try All Combinations

⏱️ Time: O(n!) Space: O(n²)

For each person, try placing them in every possible group configuration until we find a valid arrangement. This approach explores all possible ways to partition people into groups.

Greedy Approach

⏱️ Time: O(n) Space: O(n)

This approach processes each person sequentially and greedily assigns them to the first available group of the required size. If no such group exists, create a new group. This is essentially the same as the hash map approach but emphasizes the greedy nature.

Hash Map Grouping

⏱️ Time: O(n) Space: O(n)

Use a hash map to collect people based on their required group size. When we have enough people for a complete group of any size, we immediately form that group and add it to our result.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

static int groupLists[MAX_SIZE][MAX_SIZE];
static int groupCounts[MAX_SIZE];

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int groupSizes[MAX_SIZE];
    int n;
    parseArray(line, groupSizes, &n);
    
    // Initialize group counts
    for (int i = 0; i < MAX_SIZE; i++) {
        groupCounts[i] = 0;
    }
    
    printf("[");
    int firstGroup = 1;
    
    for (int person = 0; person < n; person++) {
        int size = groupSizes[person];
        groupLists[size][groupCounts[size]++] = person;
        
        // If we have enough people for a complete group
        if (groupCounts[size] == size) {
            if (!firstGroup) printf(",");
            firstGroup = 0;
            
            printf("[");
            for (int j = 0; j < size; j++) {
                if (j > 0) printf(",");
                printf("%d", groupLists[size][j]);
            }
            printf("]");
            
            groupCounts[size] = 0; // Reset for next group of this size
        }
    }
    
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

⚡ Linearithmic Space

156.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen