DAY 100 - 1282. Group the People Given the Group Size They Belong To

Hey Guys! Welcome to the 100th Day in our 100DaysOfCodeChallenge.
Before starting today's question, I would like to thank anyone who has spared time to read what I've written over the course of 100 days and anyone who reads this into the future. I won't say much but the journey has been amazing and I recommend everyone to take this challenge at least once. It's a whole another feeling of it's own.

I am going to take a quick break of a week or something probably less and I will be back but I will be writing more freely now and will try other things than Data Structures and Algorithm Articles.

Let's get back to our work, today we are going to sovle today's daily leetcode question.

Question: 1282. Group the People Given the Group Size They Belong To

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers,return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example:

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

Understanding the Problem

Before we delve into the code, let's gain a clear understanding of the problem:

• We're given an array groupSizes where groupSizes[i] represents the group size that the i-th person belongs to.

• Our task is to group people together based on their group sizes while ensuring that each group contains exactly groupSizes[i] people.

• The order of people within each group does not matter, but the order of groups in the result matters.

• From these observations it's clear to us we need to somehow maintain which indexed person it is, his groupSize and he must go into that groupSize.

Intuiton:

• By breaking down the question we realize we have to keep tracks of two things:
  First: The groupSizes of the i'th index denote the groupSize it must be in.
  Second: We also need to keep track of other members of that specific group size.

• We are related by two things, the key (size of the group) and it's members(indexes of that specific group size).

• We can simply use an unordered_map<int,vector<int>> here as it will help us keep track of both the things. Our map will store a vector containing members corresponding to our keys.

• But if we store all the members they might be greater than the groupSize and we might need to make more groups for it.

Let's head down to the approach we used to solve this:

The Approach

To solve this problem efficiently, we can use a systematic approach. Here's the intuition behind the approach:

1. Initialize a Data Structure: We start by initializing two data structures: a vector of vectors called result to store the final answer and an unordered map called mp to help us organize the people based on their group sizes.

2. Iterate Through the Input Array: We traverse the groupSizes array using a loop. In each iteration, we perform the following steps:

• Extract the key, which represents the group size for the current person.

• Add the person's index (representing a member) to the corresponding group in our mp map.

• Check if the group is now full, meaning it contains exactly key people. If so, we move all the members of that group from mp to our result vector. This ensures that we have created a complete group, and we can remove the group size from mp.

1. Return the Result: Finally, we return the result vector, which contains all the groups of people based on their group sizes.

Code:

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> result;
        unordered_map<int,vector<int>> mp;

        for(int i = 0; i < groupSizes.size(); ++i){
            int key = groupSizes[i]; //this is the groupSize for that index

            mp[key].push_back(i); //push the members of that specific group

            if (mp[key].size() == key) { // group is full so push that into our answer
                result.push_back(mp[key]);
                mp.erase(key);
            }

        }



        return result;
    }
};

Complexity Analysis:

• Time Complexity: We make a single pass through the groupSizes array, so its time complexity is O(N), where N is the length of the input array and our insertion and deletion in unordered_map is O(1). So our overall time complexity is O(N).

• Space Complexity: We use two data structures, the result vector and the mp unordered map. The space required for result is proportional to the number of groups and can be as large as N/2 in the worst case. The space used by mp is also proportional to the number of groups. Therefore, the space complexity is O(N).