Tejav
#1282

Group the People Given the Group Size They Belong To

Medium
ArrayHash TableGreedyHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a greedy approach to group people based on their required group sizes. By organizing people into buckets based on their group sizes, we can efficiently form groups without unnecessary checks.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a dictionary to hold lists of people for each group size.
  2. 2Step 2: Iterate through the groupSizes array and populate the dictionary with people IDs.
  3. 3Step 3: For each group size in the dictionary, split the list of people into groups of the required size and add them to the final result.
solution.py12 lines
1# Full working Python code
2
3def groupThePeople(groupSizes):
4    from collections import defaultdict
5    groups = defaultdict(list)
6    result = []
7    for i, size in enumerate(groupSizes):
8        groups[size].append(i)
9        if len(groups[size]) == size:
10            result.append(groups[size])
11            groups[size] = []
12    return result
ℹ

Complexity note: The complexity is O(n) because we only pass through the groupSizes array once and use a dictionary to store groups, which allows for efficient access and insertion.

  • 1Group sizes must match the number of people in each group.
  • 2Using a dictionary allows for efficient grouping based on size.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.