#1282

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Group the People Given the Group Size They Belong To

Organize people into groups based on their specified group sizes using array scanning and hash table bucketing efficiently.

array hash table greedy

Problem Statement

You are given n people labeled from 0 to n - 1 and an integer array groupSizes where groupSizes[i] represents the exact size of the group that person i must belong to. Your task is to partition all people into valid groups so that every person i is in a group containing exactly groupSizes[i] members.

Return a list of groups as arrays of person IDs. Each group must satisfy its size requirement, and all people must be included in exactly one group. Multiple valid groupings may exist, but each must obey the groupSizes constraints.

Examples

Example 1

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

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

The first group is [5]. The size is 1, and groupSizes[5] = 1. The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3. The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3. Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2

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

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

Example details omitted.

Constraints

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

Solution Approach

Bucket Person IDs by Group Size

Create a hash map where each key is a group size and each value is a list of person IDs needing that size. Iterate through groupSizes, appending each person ID to the corresponding bucket.

Form Complete Groups from Buckets

For each bucket, repeatedly extract sublists of length equal to the group size. Each sublist forms a valid group. This ensures every group matches the exact size requirement without leftover IDs.

Combine and Return All Groups

Accumulate all the formed groups into a single result list. Because each person is only added to a bucket once and groups are finalized immediately, the result satisfies all groupSizes constraints efficiently.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) because we iterate through the groupSizes array once and build groups in linear time. Space complexity is O(N) for storing person IDs in the hash map and the final list of groups.

What Interviewers Usually Probe

Do you notice that grouping by size can be handled greedily with buckets?
Watch for off-by-one errors when splitting buckets into exact group sizes.
Consider whether a single pass can build all groups without revisiting elements.

Common Pitfalls or Variants

Common pitfalls

Failing to create groups immediately when a bucket reaches its group size, causing leftover IDs.
Mixing person IDs across different group size buckets, violating size constraints.
Assuming a fixed group order instead of allowing any valid permutation.

Follow-up variants

Return groups in sorted order of their first member ID for consistent output.
Handle dynamic updates where new people join and require insertion into existing buckets.
Adapt to situations where group sizes may exceed current bucket length, requiring temporary holding lists.

FAQ

What is the main idea behind Group the People Given the Group Size They Belong To?

The key is to bucket person IDs by their group size and then greedily form complete groups from each bucket, ensuring all size constraints are met.

Can there be multiple correct outputs?

Yes, as long as each group matches its specified size, different permutations of IDs within or across groups are valid.

What pattern does this problem illustrate?

This problem exemplifies the array scanning plus hash lookup pattern where buckets track grouping requirements efficiently.

How does GhostInterview handle this problem?

GhostInterview maps IDs to buckets, forms groups as soon as a bucket is full, and compiles results automatically, preventing common pitfalls.

What is the time complexity of this approach?

The algorithm runs in O(N) time because each person ID is processed once and groups are built in linear time.

terminal

Solution

Solution 1: Hash Table or Array

We use a hash table $g$ to store which people are in each group size $groupSize$. Then we partition each group size into $k$ equal parts, with each part containing $groupSize$ people.

1

2

3

4

5

6

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        g = defaultdict(list)
        for i, v in enumerate(groupSizes):
            g[v].append(i)
        return [v[j : j + i] for i, v in g.items() for j in range(0, len(v), i)]

Continue Practicing

#1296 divide array in sets of k consecutive numbers #1338 reduce array size to the half #1386 cinema seat allocation