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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Group the People Given the Group Size They Belong To

Number: 1407

Difficulty: Medium

Paid? No

Companies: Amazon, Adobe, C3 IoT, Roblox

Problem Description

Given an integer array groupSizes where each element groupSizes[i] represents the size of the group that person i must belong to, partition all persons labeled from 0 to n - 1 into groups such that each person is in exactly one group matching the required size. Return any valid grouping.

Key Insights

  • Use a hash map to bucket persons by their required group sizes.
  • Accumulate person indices in the bucket corresponding to groupSizes[i].
  • Once a bucket reaches the size equal to its key, add that bucket as a valid group and clear it.
  • This greedy grouping ensures each group meets the constraints.

Space and Time Complexity

Time Complexity: O(n), where n is the number of persons. Space Complexity: O(n), since we use additional storage for the hashmap and the result list.

Solution

We initialize a hashmap (or dictionary) to map each required group size to a list of person indices with that requirement. As we iterate through the array:

  1. Add the current person to the corresponding bucket.
  2. If the bucket's length becomes equal to the required group size, finalize that bucket as a group, append it to the result, and reset the bucket. This approach guarantees a valid partitioning in linear time using extra space proportional to n.

Code Solutions

# Python solution with line-by-line comments

def groupThePeople(groupSizes):
    # Dictionary to store groups for each size requirement
    groups = {}
    result = []
    
    # Iterate over each person using index 'person'
    for person, size in enumerate(groupSizes):
        # Initialize the bucket for this group size if not already created
        if size not in groups:
            groups[size] = []
        # Add the current person to the bucket
        groups[size].append(person)
        
        # If the bucket reaches the required size, it forms a valid group
        if len(groups[size]) == size:
            result.append(groups[size])
            # Reset the bucket for that group size
            groups[size] = []
    
    return result

# Example usage:
groupSizes = [3,3,3,3,3,1,3]
print(groupThePeople(groupSizes))
← Back to All Questions