Group the People Given the Group Size They Belong To

Med

#1195Time: 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.1 company

Patterns

Greedy

Data structures

Array Hash Table

Companies

Roblox

Prompt

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 == n
1 <= n <= 500
1 <= 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 result to store the final groups and a boolean array visited of size n to track people already assigned to a group.
Iterate through each person i from 0 to n-1.
If person i has 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 person i to currentGroup and mark them as visited by setting visited[i] = true. d. To find the remaining size - 1 members, iterate through the people from j = i + 1 to n-1. e. If currentGroup is full (its size equals size), stop searching for more members. f. If person j has not been visited and their required group size groupSizes[j] is equal to size, add j to currentGroup and 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 the currentGroup to the result list.
After the outer loop completes, return the result list.

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<List<Integer>> groupThePeople(int[] groupSizes) {6        int n = groupSizes.length;7        List<List<Integer>> result = new ArrayList<>();8        boolean[] visited = new boolean[n];9 10        for (int i = 0; i < n; i++) {11            if (!visited[i]) {12                int size = groupSizes[i];13                List<Integer> currentGroup = new ArrayList<>();14                15                // Find members for this new group16                for (int j = i; j < n; j++) {17                    if (currentGroup.size() == size) {18                        break;19                    }20                    if (!visited[j] && groupSizes[j] == size) {21                        currentGroup.add(j);22                        visited[j] = true;23                    }24                }25                result.add(currentGroup);26            }27        }28        return result;29    }30}

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.

A much more efficient approach is to first categorize all people by their required group size using a hash map. This allows us to collect all people who belong to the same size group together. After this initial pass, we can easily form the final groups by processing these categorized lists. This can be optimized into a single pass through the input array.

Algorithm

Initialize an empty list result for the final groups and a hash map groups to store temporary groups, where the key is the group size and the value is a list of people.
Iterate through the groupSizes array with index i from 0 to n-1.
For each person i, get their required group size, size = groupSizes[i].
Use the map to get the current list of people for this size. If no list exists for this size, create a new empty one. A helper method like map.computeIfAbsent(size, k -> new ArrayList<>()) is useful here.
Add the current person i to this list.
Check if the list is now full (i.e., its size equals size).
If the group is full: a. Add a copy of this list to the result. b. Clear the list in the map so that a new group of the same size can be started. groups.get(size).clear().
After iterating through all the people, return the result list.

Walkthrough

The core idea is to use a hash map to keep track of partially filled groups. The keys of the map are the group sizes, and the values are the lists of people currently assigned to a group of that size.

We iterate through the input array groupSizes just once. For each person i, we look at their required group size s = groupSizes[i]. We find the list in our map corresponding to size s (or create it if it's the first person we've seen for that size). We add person i to this list. Immediately after adding, we check if this list has become full (i.e., its size is now equal to s). If it is full, we add a copy of this list to our final result list and then clear the list in the map. This makes the map ready to start collecting people for the next group of size s. This single-pass approach is both elegant and efficient.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public List<List<Integer>> groupThePeople(int[] groupSizes) {8        List<List<Integer>> result = new ArrayList<>();9        Map<Integer, List<Integer>> groups = new HashMap<>();10 11        for (int i = 0; i < groupSizes.length; i++) {12            int size = groupSizes[i];13            14            // Get the list for the current size, or create it if it doesn't exist.15            groups.computeIfAbsent(size, k -> new ArrayList<>());16            List<Integer> currentGroup = groups.get(size);17            18            // Add the current person to the group.19            currentGroup.add(i);20            21            // If the group is full, add it to the result and reset for the next group.22            if (currentGroup.size() == size) {23                result.add(new ArrayList<>(currentGroup)); // Add a copy24                currentGroup.clear(); // Clear for the next group of this size25            }26        }27        return result;28    }29}

Complexity

Time

O(n). We iterate through the `groupSizes` array exactly once. Each operation inside the loop (map access, list add, list clear) takes, on average, constant time. This makes the overall time complexity linear with respect to the number of people.

Space

O(n). The hash map `groups` can, in the worst case, store all `n` people before they are formed into complete groups and cleared. The `result` list also stores all `n` people. Therefore, the space complexity is linear.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(n).
Processes the input in a single, elegant pass.
The logic is clean and directly models the grouping process.

Cons

Requires extra space for the hash map, which can store up to n elements in intermediate steps.

Solutions

Solution

1class 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 ; } }

1class Solution {2public:3  vector<vector<int>> groupThePeople(vector<int> &groupSizes) {4    int n = groupSizes.size();5    vector<vector<int>> g(n + 1);6    for (int i = 0; i < n; ++i)7      g[groupSizes[i]].push_back(i);8    vector<vector<int>> ans;9    for (int i = 0; i < g.size(); ++i) {10      for (int j = 0; j < g[i].size(); j += i) {11        vector<int> t(g[i].begin() + j, g[i].begin() + j + i);12        ans.push_back(t);13      }14    }15    return ans;16  }17};

1class Solution : def groupThePeople ( self , groupSizes : List [ int ]) -> List [ List [ int ]]: g = defaultdict ( list ) for i , v in enumerate ( groupSizes ): g [ v ]. append ( i ) return [ v [ j : j + i ] for i , v in g . items () for j in range ( 0 , len ( v ), i )]

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.

← Previous

Previous problem

Next problem