Problem Description

The problem, "Group the People Given the Group Size They Belong To", asks you to partition a list of people into groups based on their required group sizes. You are given an array groupSizes of length n, where groupSizes[i] is the size of the group that person i must be in. Each person must belong to exactly one group, and each group must have exactly as many members as the group size required by each member in it.

• Each person is represented by their index (from 0 to n-1).
• All groups formed must have exactly the number of people as required by each member’s groupSizes value.
• No person can be in more than one group, and each person must be included in exactly one group.
• It is guaranteed that at least one valid grouping exists for the input.

The task: Return a list of groups, where each group is a list of people's indices. The order of groups and the order within each group does not matter.

Thought Process

At first glance, one might consider brute-forcing all possible ways to divide people into groups and checking if each group satisfies the size requirements. However, this approach would be highly inefficient due to the combinatorial explosion as the number of people increases.

Instead, we notice that the problem is fundamentally about grouping people by their required group sizes. If several people need to be in a group of size 3, we can collect them and form groups of 3 as we go. Thus, we can use a mapping (like a hash map or dictionary) to collect people needing the same group size, and whenever we have enough people for a group, we finalize that group.

The key insight is to process the groupSizes array once, assigning each person to a bucket based on their required group size, and then partition those buckets into groups of the required size.

Solution Approach

Let's break down the optimized algorithm step-by-step:

1. Initialize a mapping: Use a hash map (dictionary) size_to_people where the key is the group size, and the value is a list of person indices who require that group size.
2. Iterate through the input: For each person i in groupSizes, append i to the list for groupSizes[i] in size_to_people.
3. Form groups: For each group size in size_to_people:
   • Take the list of people requiring that group size.
   • Partition this list into sublists of length equal to the group size.
   • Add each of these sublists to the final result.
4. Return the result: The result is a list of groups, each group being a list of indices.

This approach ensures that each person is placed in exactly one group, and all group size constraints are satisfied.

Example Walkthrough

Let's walk through an example with groupSizes = [3,3,3,3,3,1,3]:

1. Mapping people to group sizes:
   • Person 0: group size 3 → [0]
   • Person 1: group size 3 → [0,1]
   • Person 2: group size 3 → [0,1,2]
   • Person 3: group size 3 → [0,1,2,3]
   • Person 4: group size 3 → [0,1,2,3,4]
   • Person 5: group size 1 → [5]
   • Person 6: group size 3 → [0,1,2,3,4,6]
   At the end, we have:
   • Group size 3: [0,1,2,3,4,6]
   • Group size 1: [5]
2. Partition into groups:
   • For group size 3: partition [0,1,2,3,4,6] into [0,1,2] and [3,4,6]
   • For group size 1: just [5]
3. Final result: [[0,1,2], [3,4,6], [5]] (order may vary)

Each group contains only people requiring that group size, and no person appears in more than one group.

Time and Space Complexity

Brute-force approach: Trying all possible groupings and checking validity would be factorial time, which is infeasible for large inputs.

Optimized approach:

• Time Complexity: O(n), where n is the length of groupSizes. We process each person once to build the mapping, and again to partition into groups.
• Space Complexity: O(n), for storing the mapping and the final groups.

Summary

The problem is elegantly solved by grouping people according to their required group sizes and partitioning each group as soon as enough members are collected. This avoids brute-force enumeration and leverages hash maps for efficient grouping. The algorithm is both simple and powerful, running in linear time and space, and guarantees that all constraints are satisfied with minimal code.

Code Implementation

from collections import defaultdict

class Solution:
    def groupThePeople(self, groupSizes):
        size_to_people = defaultdict(list)
        result = []
        
        for i, size in enumerate(groupSizes):
            size_to_people[size].append(i)
            if len(size_to_people[size]) == size:
                result.append(size_to_people[size][:])
                size_to_people[size] = []
        return result
    

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> size_to_people;
        vector<vector<int>> result;
        for (int i = 0; i < groupSizes.size(); ++i) {
            int size = groupSizes[i];
            size_to_people[size].push_back(i);
            if (size_to_people[size].size() == size) {
                result.push_back(size_to_people[size]);
                size_to_people[size].clear();
            }
        }
        return result;
    }
};
    

import java.util.*;

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

        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            sizeToPeople.putIfAbsent(size, new ArrayList<>());
            sizeToPeople.get(size).add(i);

            if (sizeToPeople.get(size).size() == size) {
                result.add(new ArrayList<>(sizeToPeople.get(size)));
                sizeToPeople.get(size).clear();
            }
        }
        return result;
    }
}
    

/**
 * @param {number[]} groupSizes
 * @return {number[][]}
 */
var groupThePeople = function(groupSizes) {
    const sizeToPeople = {};
    const result = [];
    for (let i = 0; i < groupSizes.length; i++) {
        const size = groupSizes[i];
        if (!(size in sizeToPeople)) sizeToPeople[size] = [];
        sizeToPeople[size].push(i);
        if (sizeToPeople[size].length === size) {
            result.push([...sizeToPeople[size]]);
            sizeToPeople[size] = [];
        }
    }
    return result;
};