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] <= nIn #1282 Group the People Given the Group Size They Belong To, each person specifies the size of the group they must belong to. The goal is to partition all people into valid groups that exactly match their required sizes.
A common strategy uses a hash table to collect people by their required group size. As you iterate through the array, append each person's index to a bucket corresponding to their group size. Once the bucket reaches the required size, you finalize that group and add it to the result. Then clear or recreate the bucket to continue forming additional groups of the same size.
This method works well because the constraint guarantees that a valid grouping exists. The approach behaves like a greedy grouping process, forming groups immediately when enough members accumulate. Using a map such as size -> list of indices ensures efficient tracking while scanning the array only once.
The overall performance is linear since each person is processed exactly once.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Greedy Group Formation | O(n) | O(n) |
Fisher Coder
Use these hints if you're stuck. Try solving on your own first.
Put people's IDs with same groupSize into buckets, then split each bucket into groups.
Greedy fill until you need a new group.
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.
1var groupThePeople = function(groupSizes) {
2 const sizeToPeople = new Map();
3 const result = [In JavaScript, we use a Map to track lists of people by their group size. As we add people, the lists are checked for completeness, and full lists are appended to the result, after which the entry is cleared.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the problem can be viewed as a greedy grouping process. Once enough people accumulate for a specific group size, you immediately finalize that group instead of delaying the decision.
Problems involving grouping with hash maps and greedy logic are common in FAANG-style interviews. While the exact question may vary, the underlying idea of grouping elements based on constraints appears frequently.
A hash table (or dictionary) is the most suitable data structure. It maps each group size to a temporary list of people waiting to form that group, enabling efficient insertion and group completion checks.
The optimal approach uses a hash map that groups people by their required group size. As soon as the collected indices for a size reach that size, a group is finalized and added to the result. This allows the problem to be solved in a single pass with linear time complexity.
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.