Leetcode 1282: Group the People Given the Group Size They Belong To

Input: You are given an array where each element represents the group size that each person is assigned to.

Example: Input: groupSizes = [3,3,3,3,3,1,3]

Constraints:

• 1 <= n <= 500

• 1 <= groupSizes[i] <= n

Output: Return a list of lists, where each list represents a group containing the people who belong to that group.

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

Constraints:

• Each person should appear in exactly one group.

• The number of people in each group must match the values in the input array.

Goal: To group people based on the sizes specified in the input array.

Steps:

• Iterate through the input array and maintain a list of people for each group size.

• Once a group reaches the required size, add it to the result and start a new group for the next people.

Goal: Ensure each person is placed in exactly one group and no group exceeds its specified size.

Steps:

• The groupSizes array has length n.

• 1 <= n <= 500

• 1 <= groupSizes[i] <= n

Assumptions:

• The input array will always contain valid values and have a valid solution.

• Input: Input: groupSizes = [3,3,3,3,3,1,3]

• Explanation: In this example, we must group people such that the sizes of the groups correspond to the values in the groupSizes array. For example, the first three people (0, 1, and 2) must form a group of size 3, while the last person (5) must be in a group of size 1.

Approach: The solution uses a greedy approach where people are grouped in batches according to the specified group sizes.

Observations:

• We need to keep track of people who are yet to be grouped based on their required group size.

• Iterate through the groupSizes array, and as each person is processed, maintain a list of current groups. Once a group reaches its specified size, move on to the next group.

Steps:

• Iterate through the `groupSizes` array.

• For each group size, add the corresponding person to the list of the appropriate group.

• Once a group reaches the required size, add it to the result list and start a new group.

Empty Inputs:

• If the groupSizes array is empty, there should be no groups formed.

Large Inputs:

• Ensure that the solution efficiently handles input sizes up to the maximum allowed (500).

Special Values:

• If all people are required to be in groups of size 1, each person will form their own group.

Constraints:

• Each group will always have the correct number of people as per the input constraints.

vector<vector<int>> groupThePeople(vector<int>& gz) {
    vector<vector<int>> res, gzs(gz.size() + 1);
    for(auto i = 0; i < gz.size(); i++) {
        gzs[gz[i]].push_back(i);
        if(gzs[gz[i]].size() == gz[i]) {
            res.push_back({});
            swap(res.back(), gzs[gz[i]]);
        }
    }
    return res;
}

1 : Function Definition

vector<vector<int>> groupThePeople(vector<int>& gz) {

Defines a function that takes a vector of group sizes as input and returns grouped indices.

2 : Variable Initialization

    vector<vector<int>> res, gzs(gz.size() + 1);

Initializes a result vector and an auxiliary grouping vector for grouping based on sizes.

3 : Loop Setup

    for(auto i = 0; i < gz.size(); i++) {

Loops through each index in the group size vector.

4 : Group Assignment

        gzs[gz[i]].push_back(i);

Assigns the current index to the group corresponding to its size.

5 : Conditional Check

        if(gzs[gz[i]].size() == gz[i]) {

Checks if the current group has reached the required size.

6 : Add Group to Result

            res.push_back({});

Creates a new subgroup in the result vector.

7 : Swap Operation

            swap(res.back(), gzs[gz[i]]);

Swaps the last group in the result vector with the filled group.

8 : Return Statement

    return res;

Returns the final grouped result vector.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The algorithm processes each person once, so the time complexity is O(n), where n is the number of people.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) because we store the groups in a result list.

Leetcode 1282: Group the People Given the Group Size They Belong To

Explore →