We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Group the People Given the Group Size They Belong To

Difficulty: Medium

Problem Description

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. The task is to 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.

Key Insights

  • Each person has a unique ID and belongs to a group of a specific size.
  • The solution can involve grouping people incrementally based on their required group sizes.
  • A hash table (dictionary) can be useful to keep track of people belonging to each group size.
  • Once a group reaches its required size, it can be added to the final result.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a hash table (or dictionary) to map group sizes to lists of people. We'll iterate through the groupSizes array and for each person, add their ID to the corresponding list based on their group size. When a list reaches the required size, we add it to the final result and reset that list for future groups.

Code Solutions

def groupThePeople(groupSizes):
    from collections import defaultdict
    
    groups = defaultdict(list)
    result = []
    
    # Group people by their required group size
    for person_id, group_size in enumerate(groupSizes):
        groups[group_size].append(person_id)
        
        # If the group is full, add it to the result
        if len(groups[group_size]) == group_size:
            result.append(groups[group_size])
            groups[group_size] = []  # Reset for future groups
            
    return result
← Back to All Questions