Group the People Given the Group Size They Belong To Solution
Group the People Given the Group Size They Belong To solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Group the People Given the Group Size They Belong To is a medium coding problem on arrays, hash table and greedy, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Greedy
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n people numbered 0 to n - 1, and groupSizes[i] is the size of the group person i must belong to.
Return a valid grouping. To make the answer unique, build it this way: walk the people in increasing order, adding each to the open group for their size; the moment a group reaches its size, it is closed and appended to the answer.
Example 1
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[0,1,2],[5],[3,4,6]]
Explanation: People 0-2 close the first group of three; person 5 forms a group alone; 3, 4 and 6 close the last group.
Example 2
Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[2,3,4],[0,5]]
Explanation: Person 1 closes first because their group needs only one member.
Example 3
Input: groupSizes = [1,1]
Output: [[0],[1]]
Constraints
groupSizes.length == n1 <= n <= 5001 <= groupSizes[i] <= nThe input always admits a valid grouping.
Hints for Group the People Given the Group Size They Belong To
Hint 1
Bucket the people by the group size they require.
Hint 2
Each bucket fills up and empties repeatedly — flush it every time it reaches the required size.
Hint 3
Appending at the moment of closure is what makes the answer order deterministic.
How to solve Group the People Given the Group Size They Belong To
People who need the same group size are interchangeable, so bucket by size and emit a group whenever a bucket is full. Nothing has to be planned ahead.
Approach
- Keep a map from required size to the list of people waiting at that size.
- Walk the people in index order, appending each to their bucket.
- When a bucket's length equals its size, append it to the answer and clear it.
Why it works
The input guarantees each size's population is a multiple of that size, so every bucket empties exactly. Emitting greedily is valid because any full bucket is already a legal group, and the indices left behind can still be grouped among themselves.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Reusing the same list object after flushing mutates a group already placed in the answer — clear by assigning a fresh list.
- Collecting all buckets first and slicing at the end gives a different (also valid) order, which this statement's determinism rule rules out.
Reference solution
Python
from typing import List
def groupThePeople(groupSizes: List[int]) -> List[List[int]]:
pending = {}
out = []
for i, size in enumerate(groupSizes):
pending.setdefault(size, []).append(i)
if len(pending[size]) == size:
out.append(pending[size])
pending[size] = []
return outJava
public static int[][] groupThePeople(int[] groupSizes) {
Map<Integer, List<Integer>> pending = new HashMap<>();
List<int[]> out = new ArrayList<>();
for (int i = 0; i < groupSizes.length; i++) {
int size = groupSizes[i];
List<Integer> bucket = pending.computeIfAbsent(size, z -> new ArrayList<>());
bucket.add(i);
if (bucket.size() == size) {
int[] group = new int[size];
for (int t = 0; t < size; t++) group[t] = bucket.get(t);
out.add(group);
pending.put(size, new ArrayList<>());
}
}
return out.toArray(new int[0][]);
}C++
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
unordered_map<int, vector<int>> pending;
vector<vector<int>> out;
for (int i = 0; i < (int) groupSizes.size(); i++) {
int size = groupSizes[i];
pending[size].push_back(i);
if ((int) pending[size].size() == size) {
out.push_back(pending[size]);
pending[size].clear();
}
}
return out;
}JavaScript
var groupThePeople = function(groupSizes) {
var pending = {}, out = [];
for (var i = 0; i < groupSizes.length; i++) {
var size = groupSizes[i];
var key = String(size);
if (pending[key] === undefined) pending[key] = [];
pending[key].push(i);
if (pending[key].length === size) {
out.push(pending[key]);
pending[key] = [];
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets