# Group the People Given the Group Size They Belong To
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to)
Canonical: https://scaleengineer.com/dsa/problems/group-the-people-given-the-group-size-they-belong-to
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox)
---
## Problem
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
## Brute-Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. 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.
2. Iterate through each person `i` from `0` to `n-1`.
3. 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.
4. After the outer loop completes, return the `result` list.

## Efficient Grouping with a Hash Map
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> groups = new HashMap<>();

        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            
            // Get the list for the current size, or create it if it doesn't exist.
            groups.computeIfAbsent(size, k -> new ArrayList<>());
            List<Integer> currentGroup = groups.get(size);
            
            // Add the current person to the group.
            currentGroup.add(i);
            
            // If the group is full, add it to the result and reset for the next group.
            if (currentGroup.size() == size) {
                result.add(new ArrayList<>(currentGroup)); // Add a copy
                currentGroup.clear(); // Clear for the next group of this size
            }
        }
        return result;
    }
}
```
### Algorithm
1. 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.
2. Iterate through the `groupSizes` array with index `i` from `0` to `n-1`.
3. For each person `i`, get their required group size, `size = groupSizes[i]`.
4. 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.
5. Add the current person `i` to this list.
6. Check if the list is now full (i.e., its size equals `size`).
7. 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()`.
8. After iterating through all the people, return the `result` list.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> groupThePeople(vector<int> &groupSizes) {
    int n = groupSizes.size();
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n; ++i)
      g[groupSizes[i]].push_back(i);
    vector<vector<int>> ans;
    for (int i = 0; i < g.size(); ++i) {
      for (int j = 0; j < g[i].size(); j += i) {
        vector<int> t(g[i].begin() + j, g[i].begin() + j + i);
        ans.push_back(t);
      }
    }
    return ans;
  }
};

```

### Python

```python
class 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 )]
```