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.
Example 1:
Input: groupSizes = [3,3,3,3,3,1,3] Output: [[5],[0,1,2],[3,4,6]] Explanation: 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]]
Constraints:
groupSizes.length == n1 <= n <= 5001 <= groupSizes[i] <= nProblem Overview: You get an array groupSizes where groupSizes[i] is the required size of the group that person i must belong to. The task is to split people into groups so that each person appears in exactly one group and every group’s size matches the value specified for all its members.
The key observation: people who request the same group size can be grouped together, but only up to that exact size. Once a group reaches its required size, it must be finalized and a new group started.
Approach 1: HashMap-based Grouping (O(n) time, O(n) space)
Use a hash map where the key is the required group size and the value is a temporary list of people currently forming a group of that size. Iterate through the array once. For each person i, append their index to the list mapped by groupSizes[i]. Whenever the list length equals the required group size, push that list into the result and reset the bucket for that size.
The insight is that people requesting the same group size are interchangeable. The hash map lets you quickly collect them until the quota is satisfied. Each index is processed once, and each insertion into a group happens exactly once, giving O(n) time complexity and O(n) auxiliary space for the map and result structure. This approach relies heavily on efficient hash lookups and is a common pattern when solving grouping problems using a hash table.
Approach 2: Index-Based Direct Group Allocation (O(n) time, O(n) space)
Another option avoids maintaining growing lists inside a map. Iterate through the array and track partially built groups indexed by required size. Maintain an array or dictionary where each entry stores the current partially filled group for that size. When a new index is processed, append it to the active group for that size.
If the group reaches its required capacity, move it directly to the result and create a fresh empty container for that size. This technique still processes each person exactly once and performs constant-time updates, so the overall complexity remains O(n) time with O(n) space.
The approach emphasizes simple index handling rather than repeated map lookups. It works well when the implementation language supports efficient dynamic lists. Conceptually it combines ideas from array iteration and greedy grouping—forming groups immediately when their size requirement is satisfied.
Recommended for interviews: The HashMap-based grouping approach is what most interviewers expect. It demonstrates the ability to translate grouping constraints into a hash bucket structure and manage dynamic lists efficiently. Explaining a naive idea first (trying to search for valid groups repeatedly) shows understanding, but the optimal O(n) hash map solution shows strong problem decomposition and data structure choice.
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.
We use a defaultdict to store lists of people who should be grouped together. As we iterate over the people, we add them to the appropriate list based on their required group size. If a list reaches the correct length, it is appended to the result, and the list is reset for new entries.
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.
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 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.
The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements.
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.
Since the range of n in the problem is small, we can also directly create an array of size n+1 to store the data, which is more efficient.
Time complexity is O(n), and space complexity is O(n). Here, n is the length of groupSizes.
| Approach | Complexity |
|---|---|
| HashMap-based Grouping | 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. |
| Index-Based Direct Group Allocation | The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements. |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap-based Grouping | O(n) | O(n) | Best general solution. Simple grouping using hash buckets for each required size. |
| Index-Based Direct Group Allocation | O(n) | O(n) | When you want fewer map operations and straightforward index tracking. |
Group the People Given the Group Size They Belong To | Dry Run | LYFT | Leetcode - 1282 • codestorywithMIK • 6,528 views views
Watch 9 more video solutions →Practice Group the People Given the Group Size They Belong To with our built-in code editor and test cases.
Practice on FleetCode