Group the People Given the Group Size They Belong To

Group the People Given the Group Size They Belong To

What is this problem about?

The Group the People Given the Group Size They Belong To coding problem gives you an array groupSizes where groupSizes[i] represents the exact size of the group that person i must be in. You need to return a list of groups such that every person is in a group of their required size. The problem guarantees that a valid grouping always exists.

Why is this asked in interviews?

Meta and Amazon ask this Hash Table and Greedy interview pattern to test your ability to organize data based on constraints. It’s a "Medium" problem that evaluates whether you can use a dictionary/map to accumulate items until a condition (group size) is met, and then "flush" them to a result list. It checks your understanding of dynamic grouping.

Algorithmic pattern used

The problem uses a Hash Map with a Greedy "Flush".

1. Create a Hash Map where the key is the groupSize and the value is a list of people (IDs) who belong to a group of that size.
2. Iterate through the people. For person i with size s, append i to map[s].
3. Check if map[s].length == s. If the list has reached the required capacity, the group is "full."
4. Remove this full list from the map, add it to your final results array, and initialize a new empty list in the map for s to catch future people with the same size requirement.

Example explanation

groupSizes = [3, 3, 3, 3, 3, 1, 3]

1. i=0 (size 3): map[3] = [0].
2. i=1 (size 3): map[3] = [0, 1].
3. i=2 (size 3): map[3] = [0, 1, 2]. Full! Add to result, reset map[3] = [].
4. i=3 (size 3): map[3] = [3].
5. i=4 (size 3): map[3] = [3, 4].
6. i=5 (size 1): map[1] = [5]. Full! Add to result, reset map[1] = [].
7. i=6 (size 3): map[3] = [3, 4, 6]. Full! Add to result. Result: [[0, 1, 2], [5], [3, 4, 6]].

Common mistakes candidates make

• Sorting First: Trying to sort the input array. While sorting by group size works, keeping track of the original indices becomes cumbersome. The Hash Map approach is $O(N)$ and preserves indices naturally.
• Flushing at the End: Accumulating all people into massive lists (e.g., map[3] = [0, 1, 2, 3, 4, 6]) and then writing a second loop to chunk them into sizes of 3. Flushing during the initial iteration is cleaner and saves memory.

Interview preparation tip

Whenever you need to chunk items into fixed sizes based on a shared property, the "Append and Flush" pattern using a Hash Map is the most efficient and readable solution.