Group the People Given the Group Size They Belong To
MedPrompt
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] <= n
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through each person and, if they haven't been assigned to a group yet, forming a new group for them. For each new group, we scan the remaining people to find others who fit the same group size requirement. This is a straightforward but inefficient method.
Algorithm
- Initialize an empty list
resultto store the final groups and a boolean arrayvisitedof sizento track people already assigned to a group. - Iterate through each person
ifrom0ton-1. - If person
ihas not been visited (visited[i]is false): a. Get the required group size,size = groupSizes[i]. b. Create a new temporary list,currentGroup. c. Add personitocurrentGroupand mark them as visited by settingvisited[i] = true. d. To find the remainingsize - 1members, iterate through the people fromj = i + 1ton-1. e. IfcurrentGroupis full (its size equalssize), stop searching for more members. f. If personjhas not been visited and their required group sizegroupSizes[j]is equal tosize, addjtocurrentGroupand mark them as visited. g. After the inner loop finishes (either by finding a full group or by reaching the end of the array), add thecurrentGroupto theresultlist. - After the outer loop completes, return the
resultlist.
Walkthrough
We use a boolean array, visited, to keep track of people who have already been placed in a group. We iterate through each person from i = 0 to n-1. If person i has not been visited, we know they need to be in a new group. We find out the required size for this group, size = groupSizes[i], and create a new list called currentGroup. We add person i to this group and mark them as visited. Then, we start a second, nested loop to find the other size - 1 members. This inner loop scans the rest of the people array. If it finds a person j who hasn't been visited and needs to be in a group of the same size, we add them to currentGroup and mark them as visited. We continue this until currentGroup is full. Once full, the group is added to our final result list. This process is repeated until every person has been assigned to a group.
import java.util.ArrayList;import java.util.List; class Solution { public List<List<Integer>> groupThePeople(int[] groupSizes) { int n = groupSizes.length; List<List<Integer>> result = new ArrayList<>(); boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (!visited[i]) { int size = groupSizes[i]; List<Integer> currentGroup = new ArrayList<>(); // Find members for this new group for (int j = i; j < n; j++) { if (currentGroup.size() == size) { break; } if (!visited[j] && groupSizes[j] == size) { currentGroup.add(j); visited[j] = true; } } result.add(currentGroup); } } return result; }}Complexity
Time
O(n^2). The outer loop runs `n` times. For each person `i` that starts a new group, the inner loop may scan the rest of the array. This nested structure leads to a quadratic time complexity in the worst-case scenario.
Space
O(n). We use a boolean array `visited` of size `n`. The `result` list also stores `n` elements in total across all groups, contributing O(n) space.
Trade-offs
Pros
Conceptually simple and easy to follow.
Does not require complex data structures like a hash map.
Cons
Highly inefficient with a time complexity of O(n^2), which is slow for larger inputs.
Repeatedly scans portions of the input array to find matching group members, leading to redundant work.
Solutions
Solution
class Solution { public List < List < Integer >> groupThePeople ( int [] groupSizes ) { int n = groupSizes . length ; List < Integer >[] g = new List [ n + 1 ]; Arrays . setAll ( g , k -> new ArrayList <>()); for ( int i = 0 ; i < n ; ++ i ) { g [ groupSizes [ i ]]. add ( i ); } List < List < Integer >> ans = new ArrayList <>(); for ( int i = 0 ; i < g . length ; ++ i ) { List < Integer > v = g [ i ]; for ( int j = 0 ; j < v . size (); j += i ) { ans . add ( v . subList ( j , j + i )); } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.