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] <= nThis 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.
C++
Java
C#
JavaScript
C
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.
C++
Java
C#
JavaScript
C
The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements.
| 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. |
LeetCode 1282: Group the People Given the Group Size They Belong To - Interview Prep Ep 24 • Fisher Coder • 3,824 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