Group the People Given the Group Size They Belong To

Problem Description

Ah, the classic dilemma of organizing a party! Imagine you’re hosting a gathering, and you have a bunch of friends who all want to hang out in groups based on their preferences. Some want to be in groups of 2, others in groups of 3, and so on. But here’s the kicker: you can’t just throw them all together and hope for the best! You need to group them according to their specified sizes.

In the LeetCode problem “Group the People Given the Group Size They Belong To,” you’re given an array where each element represents the size of the group that the person at that index wants to be in. Your task is to return a list of groups, where each group contains the indices of the people in that group.

So, if you have a friend who insists on being in a group of 4, you better make sure they’re not left hanging with just one other person. Otherwise, they might just sulk in the corner with their drink!

Code Solution


class Solution {
 public:
  vector> groupThePeople(vector& groupSizes) {
    vector> ans;
    unordered_map> groupSizeToIndices;

    for (int i = 0; i < groupSizes.size(); ++i)
      groupSizeToIndices[groupSizes[i]].push_back(i);

    for (const auto& [groupSize, indices] : groupSizeToIndices) {
      vector groupIndices;
      for (const int index : indices) {
        groupIndices.push_back(index);
        if (groupIndices.size() == groupSize) {
          ans.push_back(groupIndices);
          groupIndices.clear();
        }
      }
    }

    return ans;
  }
};

Approach

The approach taken in this solution is straightforward yet effective. First, we create a mapping of group sizes to the indices of the people who want to be in those groups. Then, we iterate through this mapping, collecting indices until we reach the desired group size. Once we have a complete group, we add it to our answer and clear the temporary storage for the next group.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the number of people.
Space Complexity	O(n), as we store the indices in a map and the final groups in a vector.

Real-World Example

Picture this: You’re at a school reunion, and everyone is trying to form groups based on their high school cliques. The jocks want to stick together, the nerds have their own table, and the art kids are off in a corner discussing the latest trends in abstract painting. Just like in this problem, you need to ensure that each group is formed according to their preferences, or else you might end up with a very awkward situation!