Leetcode 1282. Group the People Given the Group Size They Belong To

Problem Explanation:

Given an array, groupSizes, where each element at index i represents the group size that person i belongs to. The problem involves grouping people based on the group size they belong to.

In more detail, the problem requires returning a 2D list where each subarray represents a group of people. The size of each subarray must be equal to the group size of the people in it. The group sizes can range anywhere between 1 and n.

Since each person can belong to exactly one group, a person's group can be determined by the group size at their index in the array. So, you iterate through the input array and put each person (i.e., their index) in their corresponding group. When the group is full (i.e., its size is equal to the group size), you put it in the result list and create a new group for the next people with the same group size.

For instance, consider groupSizes = [3,3,3,3,3,1,3]. The array represents a total of 7 people with their group sizes. For person 0, person 1, and person 2, their group size is 3. Hence, one possible group will be [0,1,2]. Similarly, person 5 has group size 1, hence, another possible group is [5].

Approach

The problem can be solved using a Hash Table and Array data structure. The Hash Table is used to store the group members that haven't been put into the result list yet. The Array is used to store the answer, which is a list of groups.

For each groupSize[i], put i into the Hash Table with the key groupSize[i]. When the group is full, put the group indices from the Hash Table into the result list and start a new group.

C++ Solution:

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

Python Solution:

1
2python
3class Solution:
4    def groupThePeople(self, groupSizes):
5        ans = []
6        groupSizeToIndices = {}
7        for i, groupSize in enumerate(groupSizes):
8            if groupSize not in groupSizeToIndices:
9                groupSizeToIndices[groupSize] = []
10            groupSizeToIndices[groupSize].append(i)
11            if len(groupSizeToIndices[groupSize]) == groupSize:
12                ans.append(groupSizeToIndices[groupSize])
13                groupSizeToIndices[groupSize] = []
14        return ans

Java Solution:

1
2java
3import java.util.*;
4
5class Solution {
6    public List<List<Integer>> groupThePeople(int[] groupSizes) {
7        List<List<Integer>> ans = new ArrayList<>();
8        Map<Integer, List<Integer>> groupSizeToIndices = new HashMap<>();
9        for (int i = 0; i < groupSizes.length; ++i) {
10            groupSizeToIndices.computeIfAbsent(groupSizes[i], k -> new ArrayList<>()).add(i);
11            if (groupSizeToIndices.get(groupSizes[i]).size() == groupSizes[i]) {
12                ans.add(new ArrayList<>(groupSizeToIndices.get(groupSizes[i])));
13                groupSizeToIndices.get(groupSizes[i]).clear();
14            }
15        }
16        return ans;
17    }
18}

JavaScript Solution:

1
2javascript
3var groupThePeople = function(groupSizes) {
4    const ans = [];
5    const groupSizeToIndices = {};
6    for (let i = 0; i < groupSizes.length; ++i) {
7        if (!groupSizeToIndices[groupSizes[i]]) {
8            groupSizeToIndices[groupSizes[i]] = [];
9        }
10        groupSizeToIndices[groupSizes[i]].push(i);
11        if (groupSizeToIndices[groupSizes[i]].length === groupSizes[i]) {
12            ans.push(groupSizeToIndices[groupSizes[i]]);
13            groupSizeToIndices[groupSizes[i]] = [];
14        }
15    }
16    return ans;
17};

C# Solution:

1
2csharp
3public class Solution {
4    public IList<IList<int>> GroupThePeople(int[] groupSizes) {
5        var ans = new List<IList<int>>();
6        var groupSizeToIndices = new Dictionary<int, List<int>>();
7        for (int i = 0; i < groupSizes.Length; ++i) {
8            if (!groupSizeToIndices.ContainsKey(groupSizes[i])) {
9                groupSizeToIndices[groupSizes[i]] = new List<int>();
10            }
11            groupSizeToIndices[groupSizes[i]].Add(i);
12            if (groupSizeToIndices[groupSizes[i]].Count == groupSizes[i]) {
13                ans.Add(new List<int>(groupSizeToIndices[groupSizes[i]]));
14                groupSizeToIndices[groupSizes[i]].Clear();
15            }
16        }
17        return ans;
18    }
19}

Explanation of the Solutions

All five solutions apply the same approach of using a Hash Map to keep track of the indices that have not yet been grouped and an array to store the final groups. They follow the same steps:

1. They initialize an empty list of groups, ans, and an empty Hash Map, groupSizeToIndices.
2. They iterate over the groupSizes array. For each element groupSizes[i], they add the current index i to the list in groupSizeToIndices that correspond to the key groupSizes[i].
3. If there are groupSizes[i] elements in the same list after the addition, they add this group to the final list ans and then clear the list in groupSizeToIndices for the key groupSizes[i].
4. After the iteration, they return the final groups ans.

The C++ solution and Java solution use move(groupSizeToIndices[groupSizes[i]]) and new ArrayList<>(groupSizeToIndices.get(groupSizes[i])) respectively to avoid copying the list of group indices.

The Python and JavaScript solutions use list comprehension and uses push method respectively which shows the dynamic nature of those languages and their ability to easily handle list manipulations.

The C# solution uses List<int> to create a list of integers, and checks if the key exists in the dictionary before adding i to its associated value. This showcases the language's robust handling of generic types and its explicit handling of possible null reference situations.

All solutions have a time complexity of O(n), where n is the size of the input array, and a space complexity of O(n), due to the use of extra data structure to store the indices and the groups. This ensures efficiency even for large input arrays.