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

Difficulty: interview

Starter code:

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
#         mine
#         res = collections.defaultdict(list)
#         res_return = []
#         for i,j in enumerate(groupSizes):
#             res[j].append(i)
        
#         for j in res:
#             temp = [res[j][0:j]]
#             if len(res[j])>j:
#                 # print(j,res[j][1])
#                 # sub_nums = int(len(res[j])/j)
#                 for num in range(j,len(res[j]),j):
#                     temp = temp + [res[j][num:num+j]]
#                     # print(temp)
#                 res[j]=temp
#             res_return = res_return+temp
#         # print(res)
#         # print(res_return)
#         return res_return

        # other perple
        groups = defaultdict(list)
        result = []
        for index, size in enumerate(groupSizes):
            groups[size].append(index)
            if len(groups[size]) == size:
                result.append(groups.pop(size))
        return result

from collections import defaultdict
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        d=defaultdict(list)
        for i in range(len(groupSizes)):
            d[groupSizes[i]].append(i)
        ans=[]
        for i in range(1,max(groupSizes)+1):
            if i in d:
                for j in range(0,len(d[i]),i):
                    ans.append(d[i][j:j+i])
        return ans
        


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        sizes = {}
        for i, a in enumerate(groupSizes):
            if a in sizes:
                sizes[a].append(i)
            else:
                sizes[a] = [i]
        result = []
        
        for key in sizes.keys():
            if len(sizes[key]) % key == 0:
                result.extend([sizes[key][i*key:(i+1)*key] for i in range(len(sizes[key])//key)])
        # print(sizes)
        return result

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        
        
        # imput: [3,3,3,3,3,3,1]
        # output: [[0,1,2],[3,4,5],[6]]

        def group_by_size(size_list: List[int]) -> List[List[int]]: # [3,3,3,3,3,3,1]
            if size_list == []:
                return []
            if size_list is None:
                raise ValueError(\"bad input..\")
            ans_list, count_dict = [], {} #  [[0, 1, 2], ], {}
            for i, num in enumerate(size_list):
                if num == 0:
                    raise ValueError(\"group size has to be larger then 0\")
                if not num in count_dict:
                    count_dict[num] = [i]
                else:
                    count_dict[num].append(i)
                if len(count_dict[num]) == num:
                    ans_list.append(count_dict[num])
                    del count_dict[num]
            if len(count_dict) > 0:
                raise ValueError(\"some elements have bad values\")
            return ans_list
        
        return group_by_size(groupSizes)
            
        

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        out =[]
        temp=[]
        if len(groupSizes)>1:
            for each in range(len(groupSizes)):
                if type(groupSizes[each]) == int:
                    temp.append(each)
                    while len(temp) != groupSizes[each]:
                        for every in range(each+1,len(groupSizes)):
                            if groupSizes[each]==groupSizes[every]:
                                temp.append(every)
                                groupSizes[every]= \"x\"
                                break
                    out.append(temp)
                    temp=[]
        else:
            return [[0]]
        return out
                    
            

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        group_sizes_dict = {}
        ret_groups = []
        
        for i in range(len(groupSizes)):
            if groupSizes[i] not in group_sizes_dict:
                group_sizes_dict[groupSizes[i]] = [i]
            else:
                group_sizes_dict[groupSizes[i]].append(i)
                       
        keys = sorted(group_sizes_dict.keys())
        
        for i in keys:
            tmp_list = group_sizes_dict[i]
            print(tmp_list)
            to_add = []
            
            for j in range(len(tmp_list)):
                if (j+1) % i == 0:
                    to_add.append(tmp_list[j])
                    ret_groups.append(to_add)
                    to_add = []
                else:
                    to_add.append(tmp_list[j])
                    
                
        return ret_groups


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        restrictions = {}
        
        for unique_id in range(len(groupSizes)):
            group_size = groupSizes[unique_id]
            if group_size in restrictions:
                restrictions[group_size].append(unique_id)
            else:
                restrictions[group_size] = [unique_id]
            
        res = []
        
        for group_size in restrictions:
            unique_ids = restrictions[group_size]
            for i in range(0, len(unique_ids), group_size):
                res.append(unique_ids[i:i+group_size])
        return res

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = {}
        for i in range(0,len(groupSizes)):
            if groupSizes[i] in groups:
                groups[groupSizes[i]].append(i)
            else:
                groups[groupSizes[i]] = [i]
        #print(groups)
        
        output = []
        for i in groups:
            list1 = []
            for j in groups[i]:
                list1.append(j)
                if(len(list1) == i):
                    output.append(list1)
                    list1 = []
                    
        return output
                    
                
                
        
def main():
    groupSizes = input().split()
    sol = Solution()
    output = sol.groupThePeople(groupSizes)
    print(output)
    
    
def __starting_point():
    main()

__starting_point()

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = {}
        output = []

        for i in range(len(groupSizes)):
            belongGroupCount = groupSizes[i]
            # print(f'group: {belongGroupCount} | person i: {i}')

            existingGroup = groups.get(belongGroupCount)
            # print(f'existing: {groups}, belong: {belongGroupCount}')
            if existingGroup is None:
                groups[belongGroupCount] = []
                existingGroup = groups.get(belongGroupCount)

            existingGroup.append(i)
            if len(existingGroup) == belongGroupCount:
                output.append(existingGroup)
                groups[belongGroupCount] = []
            else:
                groups[belongGroupCount] = existingGroup

        return output

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        size_map = {}
        for idx, group_size in enumerate(groupSizes):
            if group_size not in size_map:
                size_map[group_size] = [[idx]]
            else:
                for group_list in size_map[group_size]:
                    if len(group_list) < group_size:
                        group_list.append(idx)
                        break
                else:
                    # new group list
                    size_map[group_size].append([idx])
        ret = []
        for k, v in list(size_map.items()):
            ret.extend(v)
        return ret


import collections
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        
        d = collections.defaultdict(list)
        out = []
        
        for i,ele in enumerate(groupSizes):
            
            d[ele].append(i)
            print(d)
            if len(d[ele]) == ele:
                    out.append(d[ele])
                    del d[ele]
        return out


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = {}
        
        for person, group_size in enumerate(groupSizes):
            if group_size not in groups:
                groups[group_size] = [[person]]
            else:
                for c_group in groups[group_size]:
                    if len(c_group) < group_size:
                        c_group.append(person)
                        break
                else:
                    groups[group_size].append([person])
        
        
        res = []
        
        [res.extend(v) for v in groups.values()]
        
        return res
                    
        
    
    
\"\"\"

{
    <size>: [[], []]
}


\"\"\"

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        smap = {}
        for i, s in enumerate(groupSizes):
            if s in smap:
                smap[s].append(i)
            else:
                smap[s] = [i]
        
        res = []
        for k, v in list(smap.items()):
            for i in range(0, len(v), k):
                # print(i, i+k)
                res.append(v[i:i+k])
                p = i
        return res
                


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        n = len(groupSizes)
        done = [False for _ in range(n)]
        groups = []
        for i in range(n):
            if done[i]:
                continue
                
                
            numInThisGroup = groupSizes[i]
            peopleInThisGroup = []
            for j in range(n):
                if not done[j] and groupSizes[j] == numInThisGroup:
                    peopleInThisGroup.append(j)
                    if len(peopleInThisGroup) == numInThisGroup:
                        break
                        
            groups.append(peopleInThisGroup)
            for person in peopleInThisGroup:
                done[person] = True
                
        return groups

import numpy as np
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        c = set(groupSizes)
        cn=[]
        for i in c:
            newlist = [j for j, val in enumerate(groupSizes) if val==i]
            if(len(newlist)>i):
               # n = int(len(newlist)/i)
                newlist = [newlist[j:j + i] for j in range(0,   len(newlist), i)]
                cn.extend(newlist)
            else:
                cn.append(newlist)
        return cn
            


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        
        group_dict = dict()
        
        for i in groupSizes:            
            if i in group_dict:
                group_dict[i] += 1            
            else:
                group_dict[i] = 1
        
        for i in group_dict.keys():            
            group_dict[i] = int(group_dict[i]/i)
            
        group_lists = dict()
        
        for i in group_dict.keys():     
            group_lists[i] = [[] for i in range(group_dict[i])]
            
        
        for i in range(len(groupSizes)):
            val = groupSizes[i]
            l = group_lists[val] 
            j = 0            
            while(len(l[j]) == val):
                j = j+1
            
            l[j].append(i)
        
        result = []
        
        for i in group_lists.keys():
            result.extend(group_lists[i])
        
        return result

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        memory = {}
        for i, el in enumerate(groupSizes):
            if el not in memory:
                memory[el] = [[i]]
            else:
                next_available = None
                for j in range(len(memory[el])):
                    if len(memory[el][j]) < el:
                        next_available = j

                if next_available is None:
                    memory[el].append([i])
                else:
                    memory[el][next_available].append(i)

        res = []
        for groups in memory.values():
            res.extend(groups)
        return res

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:        
        ret_lst = []
        for iGrpSize in range(len(groupSizes),0,-1):
            if iGrpSize in groupSizes:
                ppl = []
                for i in range(len(groupSizes)):
                    if groupSizes[i] == iGrpSize:
                        ppl.append(i)

                if len(ppl) > iGrpSize:
                    for i in range(0,len(ppl), iGrpSize):                        
                        ret_lst.append(ppl[i:i+iGrpSize])
                else:
                    ret_lst.append(ppl)
        return ret_lst

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        output = []
        subgroup = []
        count = 0
        leng = len(groupSizes)
        subsize = 0

        while count < leng:
            size = min(groupSizes)
            while size in groupSizes:
                ind = groupSizes.index(size)
                subgroup.append(ind)
                groupSizes[ind] = 501
                count += 1
                subsize += 1

                if subsize % size == 0:
                    output.append(subgroup)
                    subgroup = []
                    subsize = 0

            subgroup = []
        return output

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        res = []
        d = collections.defaultdict(list)
        for i in range(len(groupSizes)):
            d[groupSizes[i]].append(i)
            if len(d[groupSizes[i]]) == groupSizes[i]:
                res.append(d[groupSizes[i]])
                d[groupSizes[i]]=[]
        
        return res

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        dic = {}
        res = []
        for i in range(len(groupSizes)):
            if groupSizes[i] == 1:
                res.append([i])
                continue
            if groupSizes[i] in dic:
                dic[groupSizes[i]].append(i)
            else:
                dic[groupSizes[i]] = [i]
            if len(dic[groupSizes[i]]) == groupSizes[i]:
                res.append(dic[groupSizes[i]])
                dic[groupSizes[i]] = []

        return res


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        d = dict(enumerate(groupSizes))
        d = {k: v for k, v in sorted(list(d.items()), key=lambda item: item[1])}
        a = []
        b = []

        tmp = next(iter(list(d.values())))
        for k,v in list(d.items()):
            if tmp == v and (len(a) < v):
                a+=[k]
            else:
                b.append(a)
                a = []
                a+= [k]
            if k == (list(d.keys())[-1]):
                b.append(a)
            tmp = v
        return b


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = []
        sizes = {}
        for i in range(len(groupSizes)):
            if groupSizes[i] not in sizes:
                sizes[groupSizes[i]] = [i]
            else:
                sizes[groupSizes[i]].append(i)
        
        for (size, group) in list(sizes.items()):
            for i in range(0, len(group), size):
                groups.append(group[i:i+size])
            
        return groups
           


class Solution:
    def groupThePeople(self, gr: List[int]) -> List[List[int]]:
        
        res=[]
        
        for i in range(len(gr)):
            count=gr[i]
            if(count!=0):
                temp=[]
                for j in range(len(gr)):
                    for k in range(count):
                        if(gr[j]==count):
                            temp.append(j)
                            gr[j]=0
                        if(len(temp)==count):
                            res.append(temp)
                            temp=[]
                if(len(temp)!=0):
                    res.append(temp)
        return res

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        l = len(groupSizes)
        key = {}
        ans=[]
        for i in range (l):
            now = groupSizes[i]
            if now not in key.keys():                
                    key[now]=[]
                    key[now].append(i)     
            else:
                if len(key[now])!=now:
                    key[now].append(i)
                else:
                    ans.append(key[now])
                    key[now]=[]
                    key[now].append(i)
        for i in key.keys():
            if key[i] not in ans:
                ans.append(key[i])
                continue
            
                
            
        return ans

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        res = []
        dic = {}
        for idx, size in enumerate(groupSizes):
            if size == 1:
                res.append([idx])
            elif size > 1:
                if size not in dic:
                    dic[size] = [idx]
                else:
                    dic[size].append(idx)
                    if len(dic[size]) == size:
                        res.append(dic[size])
                        del dic[size]
        return res
                    
                
                


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = {}
        for id, size in enumerate(groupSizes):
            if size not in groups:
                groups[size] = [[id]]
            else:
                lastGroup = groups[size][-1]
                if len(lastGroup) != size:
                    groups[size][-1] += [id]
                else:
                    groups[size] += [[id]]
        flatList = []
        for k,v in list(groups.items()):
            flatList += v
        return flatList


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        
        groups = []
        cache = {}
        
        for i in range(len(groupSizes)):
            if groupSizes[i] not in cache:
                cache[groupSizes[i]] = []
                
            if len(cache[groupSizes[i]]) < groupSizes[i]:
                cache[groupSizes[i]].append(i)
            
            if len(cache[groupSizes[i]]) == groupSizes[i]:
                groups.append(cache[groupSizes[i]])
                cache.pop(groupSizes[i])
                
        return groups

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        d={}
        res=[]
        for i in range(len(groupSizes)):
            d[groupSizes[i]]=d.setdefault(groupSizes[i],[])+[i]
        
        for x,y in d.items():
            for j in range(0,len(y),x):
                res.append(y[j:j+x])  
        
        return res

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        groups = sorted(list(enumerate(groupSizes)), key=lambda x: x[1])
        # return groups
        out = []
        while groups:
            last_group_idx = -groups[-1][1]
            out.append([t[0] for t in groups[last_group_idx:]])
            groups = groups[:last_group_idx]
            
        return out


from collections import defaultdict


class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        all_groups = list()
        assignments = defaultdict(list)

        for i, size in enumerate(groupSizes):
            assignments[size].append(i)

        return [people[i:i+size] for size, people in list(assignments.items()) for i in range(0, len(people), size)]