Group the People Given the Group Size They Belong To — Medium Problem & Solution

Problem statement

There are n people numbered 0 to n - 1, and groupSizes[i] is the size of the group person i must belong to.

Return a valid grouping. To make the answer unique, build it this way: walk the people in increasing order, adding each to the open group for their size; the moment a group reaches its size, it is closed and appended to the answer.

Example 1

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[0,1,2],[5],[3,4,6]]
Explanation: People 0-2 close the first group of three; person 5 forms a group alone; 3, 4 and 6 close the last group.

Example 2

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[2,3,4],[0,5]]
Explanation: Person 1 closes first because their group needs only one member.

Example 3

Input: groupSizes = [1,1]
Output: [[0],[1]]

Constraints

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n
• The input always admits a valid grouping.

How to solve Group the People Given the Group Size They Belong To

People who need the same group size are interchangeable, so bucket by size and emit a group whenever a bucket is full. Nothing has to be planned ahead.

Approach

1. Keep a map from required size to the list of people waiting at that size.
2. Walk the people in index order, appending each to their bucket.
3. When a bucket's length equals its size, append it to the answer and clear it.

Why it works

The input guarantees each size's population is a multiple of that size, so every bucket empties exactly. Emitting greedily is valid because any full bucket is already a legal group, and the indices left behind can still be grouped among themselves.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Reusing the same list object after flushing mutates a group already placed in the answer — clear by assigning a fresh list.
• Collecting all buckets first and slicing at the end gives a different (also valid) order, which this statement's determinism rule rules out.

Reference solution

Python

from typing import List

def groupThePeople(groupSizes: List[int]) -> List[List[int]]:
    pending = {}
    out = []
    for i, size in enumerate(groupSizes):
        pending.setdefault(size, []).append(i)
        if len(pending[size]) == size:
            out.append(pending[size])
            pending[size] = []
    return out

JavaScript

var groupThePeople = function(groupSizes) {
    var pending = {}, out = [];
    for (var i = 0; i < groupSizes.length; i++) {
        var size = groupSizes[i];
        var key = String(size);
        if (pending[key] === undefined) pending[key] = [];
        pending[key].push(i);
        if (pending[key].length === size) {
            out.push(pending[key]);
            pending[key] = [];
        }
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium