Group the People Given the Group Size They Belong To

Medium
681.

Group the People Given the Group Size They Belong To

Group the People Given the Group Size They Belong To is a medium coding problem on arrays, hash table and greedy, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} groupSizes
 * @return {number[][]}
 */
var groupThePeople = function(groupSizes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Group the People Given the Group Size They Belong To Solution

Group the People Given the Group Size They Belong To solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Group the People Given the Group Size They Belong To is a medium coding problem on arrays, hash table and greedy, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Greedy
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Group the People Given the Group Size They Belong To

  1. Hint 1

    Bucket the people by the group size they require.

  2. Hint 2

    Each bucket fills up and empties repeatedly — flush it every time it reaches the required size.

  3. Hint 3

    Appending at the moment of closure is what makes the answer order deterministic.

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

Java

public static int[][] groupThePeople(int[] groupSizes) {
    Map<Integer, List<Integer>> pending = new HashMap<>();
    List<int[]> out = new ArrayList<>();
    for (int i = 0; i < groupSizes.length; i++) {
        int size = groupSizes[i];
        List<Integer> bucket = pending.computeIfAbsent(size, z -> new ArrayList<>());
        bucket.add(i);
        if (bucket.size() == size) {
            int[] group = new int[size];
            for (int t = 0; t < size; t++) group[t] = bucket.get(t);
            out.add(group);
            pending.put(size, new ArrayList<>());
        }
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
    unordered_map<int, vector<int>> pending;
    vector<vector<int>> out;
    for (int i = 0; i < (int) groupSizes.size(); i++) {
        int size = groupSizes[i];
        pending[size].push_back(i);
        if ((int) pending[size].size() == size) {
            out.push_back(pending[size]);
            pending[size].clear();
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets