DAY 100 - 1282. Group the People Given the Group Size They Belong To
Tags: algorithms, beginners, tutorial, 100daysofcode
Published: 2023-09-11 07:46:02

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](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/)

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

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


---

## Code:

```cpp

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