1. Group the People Given the Group Size They Belong To

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people’s IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1: Input: groupSizes = [3,3,3,3,3,1,3] Output: [[5],[0,1,2],[3,4,6]] Explanation: 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

solution1:

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        # step1 get length 1 group , append 
        size_togroup = collections.defaultdict(list)
        res = []
        for idx, each_size in enumerate(groupSizes):
            size_togroup[each_size].append(idx)
            if len(size_togroup[each_size]) == each_size:
                res.append(size_togroup.pop(each_size))
        return res

solution2(optimization):

main idea: based on solution 1, instead of check if list within one key has reached its group size limit, each time we iterate through input list, slice the final dictionary based on the group size i.

class Solution:
    # time O(N)  space O(N), where N = len(size_togroup)
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]: 
        res = []
        size_togroup = collections.defaultdict(list)
        for idx, each_size in enumerate(groupSizes):
            size_togroup[each_size].append(idx)
        for key, lst in size_togroup.items():
            for idx in range(0, len(lst), key):
                res.append(lst[idx:idx+key])
        return res