Group the People Given the Group Size They Belong To

Problem Statement

In this task, n individuals are segmented into an indeterminate number of groups. Each individual is uniquely identified by labels ranging from 0 to n - 1. You are provided with an array groupSizes where the element at each index i indicates the required size of the group for person i. For instance, if groupSizes[1] = 3, person 1 is destined to belong to a group that contains a total of three members.

You are required to orchestrate these individuals into groups in such a way that each person i finds themselves in a group of the size specified by groupSizes[i]. Every individual must be part of exactly one group. The solution must heed to the given group size constrains for each individual, and it is important to note that multiple valid groupings might exist for the same set of inputs. However, it is assured that there is at least one feasible solution that can be derived from the given inputs.

Examples

Example 1

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]].

Example 2

Input:

groupSizes = [2,1,3,3,3,2]

Output:

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

Constraints

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

Approach and Intuition

The problem prompts us to group individuals based on the size specified in the groupSizes array. We can efficiently achieve this by leveraging a dictionary (or hash map) to keep track of group members according to their intended group size. Here’s a structured method to solve the problem:

1. Begin by initializing a dictionary named groups where keys represent the group size and values are lists that store the indices (or IDs) of the individuals.

2. Traverse through the given groupSizes array. For each individual i, do the following:

   • Add the individual i to the list corresponding to their desired group size in groups.
   • Check if the number of individuals in this list reaches the group size (i.e., if the list size matches the group size key). When a list becomes full:
     • Append this completed group to the final answer list.
     • Reset the list for that particular group size in the dictionary to start forming the next group of the same size.

3. Continue the above steps until all individuals are successfully grouped.

This method efficiently groups individuals as it processes each person exactly once. It ensures that everyone is placed in a group that matches their specified size, respecting the constraints given. The ultimate complexity of this approach is O(n) since each individual's grouping is determined in a single pass of the array.

Solutions

class Solution {
public:
    vector<vector<int>> organizeGroupSizes(vector<int>& sizes) {
        vector<vector<int>> result;
        
        vector<int> sizeMap[sizes.size() + 1];
        for (int idx = 0; idx < sizes.size(); idx++) {
            sizeMap[sizes[idx]].push_back(idx);
            
            if (sizeMap[sizes[idx]].size() == sizes[idx]) {
                result.push_back(sizeMap[sizes[idx]]);
                sizeMap[sizes[idx]].clear();
            }
        }
        
        return result;
    }
};

class Solution {
    public List<List<Integer>> organizeGroups(int[] sizes) {
        List<List<Integer>> results = new ArrayList<>();
        
        Map<Integer, List<Integer>> sizeMap = new HashMap<>();
        for (int idx = 0; idx < sizes.length; idx++) {
            if (!sizeMap.containsKey(sizes[idx])) {
                sizeMap.put(sizes[idx], new ArrayList<>());
            }
            
            List<Integer> currentGroup = sizeMap.get(sizes[idx]);
            currentGroup.add(idx);

            if (currentGroup.size() == sizes[idx]) {
                results.add(currentGroup);
                sizeMap.remove(sizes[idx]);
            }
        }

        return results;
    }
}