LeetCode 1282 - Group the People Given the Group Size They Belong To
The problem gives us an array called groupSizes, where each index represents a person and each value represents the size
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy
Solution
Problem Understanding
The problem gives us an array called groupSizes, where each index represents a person and each value represents the size of the group that person must belong to.
Every person has a unique ID ranging from 0 to n - 1, where n is the length of the array. For any person i, the value groupSizes[i] tells us exactly how many people must exist in that person's group.
For example, if groupSizes[2] = 3, then person 2 must belong to a group containing exactly three people. Importantly, everyone inside that group must also have a required group size of 3.
The task is to construct and return a list of groups that satisfies all these constraints:
- Every person appears exactly once.
- Every person belongs to a group whose size matches
groupSizes[i]. - Every group contains exactly the required number of people.
- Multiple valid answers may exist, and returning any valid grouping is acceptable.
The input is an integer array:
groupSizes[i] = required size of person i's group
The output is a two-dimensional list where each inner list represents a valid group of people.
For example:
groupSizes = [3,3,3,3,3,1,3]
A valid result could be:
[[5], [0,1,2], [3,4,6]]
Person 5 requires a group size of 1, so they form a group alone. The remaining people who require size 3 are partitioned into valid groups of exactly three members.
The constraints tell us useful information about the problem scale:
1 <= n <= 5001 <= groupSizes[i] <= n
Since n is at most 500, even an O(n²) solution would likely pass, but the problem structure strongly suggests a more efficient linear-time solution.
The problem also guarantees that at least one valid solution always exists. This guarantee is important because it means we never have to worry about impossible configurations or error handling for invalid inputs.
There are several edge cases worth considering upfront. A naive implementation might struggle when many people require the same group size, because we must carefully split them into separate groups without overlap. Another tricky case is when group size equals 1, since those people must immediately form standalone groups. We also need to ensure that once a group reaches its required size, it is finalized and not accidentally modified later.
Approaches
Brute Force Approach
A brute force approach would attempt to repeatedly search for compatible people and manually construct groups.
For each unassigned person, we could search through the remaining people to find enough individuals with the same required group size. Once enough people are found, we form a group and mark those people as assigned.
This method works because people can only belong to groups matching their required size. By repeatedly scanning the list and grouping compatible individuals, we eventually assign everyone.
However, this approach becomes inefficient because each person may trigger another scan through the remaining array. In the worst case, this results in repeated traversal of the input, leading to quadratic time complexity.
For example, if many people belong to the same group size, we repeatedly search through the array to find candidates that could have been tracked more efficiently.
Optimal Approach, Hash Map Grouping
The key observation is that people with the same required group size naturally belong together.
Instead of repeatedly searching for compatible people, we can process the input once and group people by their required size using a hash map.
The hash map stores partially formed groups:
group size -> current people collected
As we iterate through the array:
- Add the current person to the corresponding temporary group.
- If the temporary group reaches the required size, finalize it.
- Add the completed group to the answer.
- Reset the temporary group for that size.
This works because all members of a valid group must share the same required size. Since the input guarantees a valid solution, once we collect exactly the required number of people, we know that group is complete.
This avoids repeated searching and processes each person exactly once.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly scans for matching people |
| Optimal | O(n) | O(n) | Uses a hash map to build groups incrementally |
Algorithm Walkthrough
Optimal Algorithm
- Create an empty result list to store completed groups.
- Create a hash map where:
key = group size
value = temporary list of people
This map helps us track partially built groups for each required size.
3. Iterate through groupSizes using both the person's index and required group size.
4. For each person:
- Add their ID to the temporary list for their required group size.
- This means we are collecting people who belong to the same type of group.
- After adding a person, check whether the temporary group has reached its required size.
For example:
group size = 3
temporary group = [0,1,2]
Since the list length is now 3, the group is complete.
6. Add the completed group to the result.
7. Reset the temporary list for that group size so future people can form additional groups of the same size.
8. Continue until all people are processed.
9. Return the completed result list.
Why it works
The algorithm maintains an important invariant:
Every temporary group contains only people requiring the same group size.
Since a group is finalized only when it reaches exactly its required size, every completed group is valid.
Additionally, every person is processed exactly once and immediately placed into exactly one temporary group. Once finalized, that group is never modified again. Because the input guarantees a valid solution, every person will eventually belong to a complete valid group.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
result = []
groups = defaultdict(list)
for person_id, group_size in enumerate(groupSizes):
groups[group_size].append(person_id)
if len(groups[group_size]) == group_size:
result.append(groups[group_size])
groups[group_size] = []
return result
The implementation starts by creating a result list that stores completed groups.
We then use defaultdict(list) to simplify hash map management. This allows us to append people to a group size bucket without checking whether the key already exists.
During iteration, enumerate(groupSizes) gives both the person's ID and required group size.
For each person, we append their ID to the corresponding temporary group:
groups[group_size].append(person_id)
Immediately after insertion, we check whether the group has reached its required size.
if len(groups[group_size]) == group_size:
If it has, the group is complete, so we append it to the result and reset the bucket for future members.
This reset step is important because there may be multiple groups with the same required size.
For example:
[3,3,3,3,3,3]
Requires two separate groups of size 3.
Finally, we return the completed result list.
Go Solution
func groupThePeople(groupSizes []int) [][]int {
result := [][]int{}
groups := make(map[int][]int)
for personID, groupSize := range groupSizes {
groups[groupSize] = append(groups[groupSize], personID)
if len(groups[groupSize]) == groupSize {
result = append(result, groups[groupSize])
groups[groupSize] = []int{}
}
}
return result
}
The Go implementation follows the exact same logic as the Python version.
Instead of defaultdict, Go uses a map[int][]int where the key is the required group size and the value is a slice of collected people.
Appending works naturally even if the slice does not yet exist:
groups[groupSize] = append(groups[groupSize], personID)
Go automatically treats missing map entries as the zero value, which for slices is nil. Appending to a nil slice works correctly, so no explicit initialization is required.
When a group becomes full, we append it to the result and replace it with a fresh empty slice.
Since n <= 500, there are no concerns about integer overflow.
Worked Examples
Example 1
Input
groupSizes = [3,3,3,3,3,1,3]
We maintain:
groups = temporary groups
result = completed groups
| Step | Person | Group Size | groups State | result |
|---|---|---|---|---|
| 1 | 0 | 3 | {3:[0]} | [] |
| 2 | 1 | 3 | {3:[0,1]} | [] |
| 3 | 2 | 3 | {3:[]} | [[0,1,2]] |
| 4 | 3 | 3 | {3:[3]} | [[0,1,2]] |
| 5 | 4 | 3 | {3:[3,4]} | [[0,1,2]] |
| 6 | 5 | 1 | {3:[3,4],1:[]} | [[0,1,2],[5]] |
| 7 | 6 | 3 | {3:[],1:[]} | [[0,1,2],[5],[3,4,6]] |
Final output:
[[0,1,2],[5],[3,4,6]]
This satisfies all constraints.
Example 2
Input
groupSizes = [2,1,3,3,3,2]
| Step | Person | Group Size | groups State | result |
|---|---|---|---|---|
| 1 | 0 | 2 | {2:[0]} | [] |
| 2 | 1 | 1 | {2:[0],1:[]} | [[1]] |
| 3 | 2 | 3 | {2:[0],3:[2]} | [[1]] |
| 4 | 3 | 3 | {2:[0],3:[2,3]} | [[1]] |
| 5 | 4 | 3 | {2:[0],3:[]} | [[1],[2,3,4]] |
| 6 | 5 | 2 | {2:[],3:[]} | [[1],[2,3,4],[0,5]] |
Final output:
[[1],[0,5],[2,3,4]]
Order does not matter.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each person is processed exactly once |
| Space | O(n) | Hash map and output storage may contain all people |
The time complexity is O(n) because we iterate through the array once, and every hash map insertion and lookup takes constant time on average.
The space complexity is O(n) because the temporary groups stored in the hash map, along with the final answer, may collectively store every person exactly once.
Test Cases
def normalize(groups):
return sorted(sorted(group) for group in groups)
solution = Solution()
# Example 1
result = solution.groupThePeople([3,3,3,3,3,1,3])
expected = [[5], [0,1,2], [3,4,6]]
assert normalize(result) == normalize(expected) # provided example 1
# Example 2
result = solution.groupThePeople([2,1,3,3,3,2])
expected = [[1], [0,5], [2,3,4]]
assert normalize(result) == normalize(expected) # provided example 2
# Single person
result = solution.groupThePeople([1])
expected = [[0]]
assert normalize(result) == normalize(expected) # minimum input size
# Everyone alone
result = solution.groupThePeople([1,1,1,1])
expected = [[0], [1], [2], [3]]
assert normalize(result) == normalize(expected) # all singleton groups
# One large group
result = solution.groupThePeople([5,5,5,5,5])
expected = [[0,1,2,3,4]]
assert normalize(result) == normalize(expected) # maximum single group
# Multiple groups of same size
result = solution.groupThePeople([2,2,2,2])
expected = [[0,1], [2,3]]
assert normalize(result) == normalize(expected) # repeated same group size
# Mixed group sizes
result = solution.groupThePeople([3,3,3,2,2,1])
expected = [[0,1,2], [3,4], [5]]
assert normalize(result) == normalize(expected) # mixed valid grouping
# Larger repeated grouping
result = solution.groupThePeople([4,4,4,4,4,4,4,4])
expected = [[0,1,2,3], [4,5,6,7]]
assert normalize(result) == normalize(expected) # multiple large groups
| Test | Why |
|---|---|
[3,3,3,3,3,1,3] |
Validates sample case with mixed group sizes |
[2,1,3,3,3,2] |
Validates second provided example |
[1] |
Tests minimum input size |
[1,1,1,1] |
Ensures singleton groups work correctly |
[5,5,5,5,5] |
Tests one large valid group |
[2,2,2,2] |
Ensures repeated same-size groups are separated properly |
[3,3,3,2,2,1] |
Tests mixed grouping behavior |
[4,4,4,4,4,4,4,4] |
Validates repeated formation of large groups |
Edge Cases
Everyone Requires a Group of Size One
Consider:
[1,1,1,1]
Every person must be placed in a standalone group. A buggy implementation might accidentally combine people together because they share the same required size.
Our implementation handles this naturally. Every time a person is added to a temporary group of size 1, the group immediately reaches completion and is added to the result.
Multiple Groups with the Same Required Size
Consider:
[3,3,3,3,3,3]
This input requires two separate groups of size 3.
A common mistake is forgetting to reset the temporary group after completion, which would incorrectly create oversized groups.
Our implementation avoids this problem by resetting:
groups[group_size] = []
after every completed group.
Large Group Consuming the Entire Input
Consider:
[5,5,5,5,5]
All people belong to one single group.
Some implementations incorrectly finalize groups too early or mishandle accumulation.
Our algorithm waits until the temporary list length exactly matches the required group size before finalizing, ensuring the entire group is constructed correctly.
Mixed Group Sizes Interleaved
Consider:
[2,3,2,3,3,2]
People requiring the same group size are not adjacent.
A naive implementation relying on consecutive elements would fail here.
The hash map approach works correctly because grouping depends only on required size, not ordering. People are accumulated into their appropriate bucket regardless of where they appear in the input array.