Group the People Given the Group Size They Belong To

medium hash map greedy

Problem

There are n people labeled 0 to n−1, and an array groupSizes where groupSizes[i] is the exact size of the group person i must end up in. Split everyone into groups so that each person lands in a group whose size matches their required size, with every person in exactly one group.

Return any valid list of groups — the input is guaranteed to admit at least one valid grouping.

InputgroupSizes = [3,3,3,3,3,1,3]

Output[[5],[0,1,2],[3,4,6]]

Person 5 wants a group of 1, so they stand alone. The other six all want groups of 3, so they split into two groups of three.

groupSizes (comma-separated, max 12 people)

def group_the_people(group_sizes):
    buckets = {}
    ans = []
    for i, size in enumerate(group_sizes):
        if size not in buckets:
            buckets[size] = []
        buckets[size].append(i)
        if len(buckets[size]) == size:
            ans.append(buckets[size])
            buckets[size] = []
    return ans

function groupThePeople(groupSizes) {
  const buckets = new Map();
  const ans = [];
  for (let i = 0; i < groupSizes.length; i++) {
    const size = groupSizes[i];
    if (!buckets.has(size)) buckets.set(size, []);
    buckets.get(size).push(i);
    if (buckets.get(size).length === size) {
      ans.push(buckets.get(size));
      buckets.set(size, []);
    }
  }
  return ans;
}

List<List<Integer>> groupThePeople(int[] groupSizes) {
    Map<Integer, List<Integer>> buckets = new HashMap<>();
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < groupSizes.length; i++) {
        int size = groupSizes[i];
        buckets.computeIfAbsent(size, k -> new ArrayList<>()).add(i);
        if (buckets.get(size).size() == size) {
            ans.add(buckets.get(size));
            buckets.remove(size);
        }
    }
    return ans;
}

vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
    unordered_map<int, vector<int>> buckets;
    vector<vector<int>> ans;
    for (int i = 0; i < (int)groupSizes.size(); i++) {
        int size = groupSizes[i];
        buckets[size].push_back(i);
        if ((int)buckets[size].size() == size) {
            ans.push_back(buckets[size]);
            buckets.erase(size);
        }
    }
    return ans;
}

Explanation

The key insight is that people who require the same group size are interchangeable — the problem accepts any valid grouping. So we never need to search or backtrack: just collect people who want size k together, and every time we have k of them, that is a finished group.

We keep a hash map of buckets keyed by group size. Scanning people left to right, person i with requirement size is appended to buckets[size]. The moment buckets[size] holds exactly size people, we flush it: push that list into the answer and reset the bucket to empty so it can start collecting the next group of the same size.

This is a greedy strategy — we close a group at the earliest possible moment — and it is safe because the input is guaranteed to be consistent: the number of people requiring size k is always a multiple of k, so every bucket ends the scan empty and nobody is left over.

Walking through groupSizes = [3,3,3,3,3,1,3]: persons 0, 1, 2 fill buckets[3], which flushes as the group [0,1,2]. Person 5 lands in buckets[1], which is instantly full and flushes as [5]. Persons 3, 4, 6 refill buckets[3] and flush as [3,4,6], giving [[0,1,2],[5],[3,4,6]] (order of groups does not matter).

Each person is appended once and moved into the answer once, and each hash-map lookup is O(1) on average, so the whole pass is O(n) time. The buckets and the answer together hold each person exactly once, so the extra space is O(n) as well.

Time: O(n) Space: O(n)