1282. Group the People Given the Group Size They Belong To LeetCode Solution
In this guide, you will get 1282. Group the People Given the Group Size They Belong To LeetCode Solution with the best time and space complexity. The solution to Group the People Given the Group Size They Belong To problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Group the People Given the Group Size They Belong To
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.
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]].
groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1282. Group the People Given the Group Size They Belong To LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
vector<vector<int>> ans;
unordered_map<int, vector<int>> groupSizeToIndices;
for (int i = 0; i < groupSizes.size(); ++i)
groupSizeToIndices[groupSizes[i]].push_back(i);
for (const auto& [groupSize, indices] : groupSizeToIndices) {
vector<int> groupIndices;
for (const int index : indices) {
groupIndices.push_back(index);
if (groupIndices.size() == groupSize) {
ans.push_back(groupIndices);
groupIndices.clear();
}
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1282. Group the People Given the Group Size They Belong To LeetCode Solution in Java
class Solution {
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> ans = new ArrayList<>();
Map<Integer, List<Integer>> groupSizeToIndices = new HashMap<>();
for (int i = 0; i < groupSizes.length; ++i) {
final int groupSize = groupSizes[i];
groupSizeToIndices.putIfAbsent(groupSize, new ArrayList<>());
groupSizeToIndices.get(groupSize).add(i);
}
for (Map.Entry<Integer, List<Integer>> entry : groupSizeToIndices.entrySet()) {
final int groupSize = entry.getKey();
List<Integer> indices = entry.getValue();
List<Integer> groupIndices = new ArrayList<>();
for (final int index : indices) {
groupIndices.add(index);
if (groupIndices.size() == groupSize) {
ans.add(new ArrayList<>(groupIndices));
groupIndices.clear();
}
}
}
return ans;
}
} // code provided by PROGIEZ
1282. Group the People Given the Group Size They Belong To LeetCode Solution in Python
class Solution:
def groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
ans = []
groupSizeToIndices = defaultdict(list)
for i, groupSize in enumerate(groupSizes):
groupSizeToIndices[groupSize].append(i)
for groupSize, indices in groupSizeToIndices.items():
groupIndices = []
for index in indices:
groupIndices.append(index)
if len(groupIndices) == groupSize:
ans.append(groupIndices.copy())
groupIndices.clear()
return ans # code by PROGIEZ
