Skip to main content
Talentd

Group the People Given the Group Size They Belong To - Solution & Explanation

MediumArrayHash TableGreedy16 min readAsked at: Amazon, Meta, Roblox +2
Practice this problem

Problem Statement

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

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. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

 

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

 

Constraints:

  • groupSizes.length == n
  • 1 <= n <= 500
  • 1 <= groupSizes[i] <= n

Approach Overview

Problem Overview: You get an array groupSizes where groupSizes[i] is the required size of the group that person i must belong to. The task is to split people into groups so that each person appears in exactly one group and every group’s size matches the value specified for all its members.

The key observation: people who request the same group size can be grouped together, but only up to that exact size. Once a group reaches its required size, it must be finalized and a new group started.

Approach 1: HashMap-based Grouping (O(n) time, O(n) space)

Use a hash map where the key is the required group size and the value is a temporary list of people currently forming a group of that size. Iterate through the array once. For each person i, append their index to the list mapped by groupSizes[i]. Whenever the list length equals the required group size, push that list into the result and reset the bucket for that size.

The insight is that people requesting the same group size are interchangeable. The hash map lets you quickly collect them until the quota is satisfied. Each index is processed once, and each insertion into a group happens exactly once, giving O(n) time complexity and O(n) auxiliary space for the map and result structure. This approach relies heavily on efficient hash lookups and is a common pattern when solving grouping problems using a hash table.

Approach 2: Index-Based Direct Group Allocation (O(n) time, O(n) space)

Another option avoids maintaining growing lists inside a map. Iterate through the array and track partially built groups indexed by required size. Maintain an array or dictionary where each entry stores the current partially filled group for that size. When a new index is processed, append it to the active group for that size.

If the group reaches its required capacity, move it directly to the result and create a fresh empty container for that size. This technique still processes each person exactly once and performs constant-time updates, so the overall complexity remains O(n) time with O(n) space.

The approach emphasizes simple index handling rather than repeated map lookups. It works well when the implementation language supports efficient dynamic lists. Conceptually it combines ideas from array iteration and greedy grouping—forming groups immediately when their size requirement is satisfied.

Recommended for interviews: The HashMap-based grouping approach is what most interviewers expect. It demonstrates the ability to translate grouping constraints into a hash bucket structure and manage dynamic lists efficiently. Explaining a naive idea first (trying to search for valid groups repeatedly) shows understanding, but the optimal O(n) hash map solution shows strong problem decomposition and data structure choice.

Approach 1: HashMap-based Grouping

This approach involves using a hashmap (or dictionary) to keep track of members that belong to groups of the same size. You iterate over the groupSizes array, and for each person, add their ID to a list associated with their required group size in the hashmap. Once a list reaches the intended group size, you add it to the result and reset the list for that group size.

We use a defaultdict to store lists of people who should be grouped together. As we iterate over the people, we add them to the appropriate list based on their required group size. If a list reaches the correct length, it is appended to the result, and the list is reset for new entries.

Code

PythonC++JavaC#JavaScriptC

Python

C++

Java

C#

JavaScript

C

Complexity

The time complexity is O(n), where n is the number of people, because each person is processed exactly once. The space complexity is also O(n), because we store the people in an intermediate dictionary before creating the result.

Try this approach in the editor →

Approach 2: Index-Based Direct Group Allocation

This approach uses direct index management without using a hashmap, iterating through the list and directly placing IDs into result groups once a correct-sized group is filled, simplifying the storage by maintaining an array or linked list for each group size.

The Python solution manages arrays directly for each group size. As people are processed, they are appended to their respective list. Once full, the list is added to the list of results and reset.

Code

PythonC++JavaC#JavaScriptC

Python

C++

Java

C#

JavaScript

C

Complexity

The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements.

Try this approach in the editor →

Approach 3: Hash Table or Array

We use a hash table g to store which people are in each group size groupSize. Then we partition each group size into k equal parts, with each part containing groupSize people.

Since the range of n in the problem is small, we can also directly create an array of size n+1 to store the data, which is more efficient.

Time complexity is O(n), and space complexity is O(n). Here, n is the length of groupSizes.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
HashMap-based Grouping

The time complexity is O(n), where n is the number of people, because each person is processed exactly once. The space complexity is also O(n), because we store the people in an intermediate dictionary before creating the result.

Index-Based Direct Group Allocation

The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements.

Hash Table or Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap-based GroupingO(n)O(n)Best general solution. Simple grouping using hash buckets for each required size.
Index-Based Direct Group AllocationO(n)O(n)When you want fewer map operations and straightforward index tracking.

Video Solution

Group the People Given the Group Size They Belong To | Dry Run | LYFT | Leetcode - 1282 • codestorywithMIK • 6,948 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Group the People Given the Group Size They Belong To easy or hard?
The problem is rated Medium on LeetCode but becomes straightforward once you recognize the grouping pattern. The main challenge is translating the constraint that every person requires a specific group size into a bucket-based solution using a hash map.
Group the People Given the Group Size They Belong To Python/Java solution
In both Python and Java, the solution typically uses a dictionary or HashMap mapping group size to a list of indices. Iterate through the array, append the index to its bucket, and once the bucket length equals the required size, add the list to the result. The algorithm runs in O(n) time and O(n) space.
How to solve Group the People Given the Group Size They Belong To in O(n)?
Iterate through the groupSizes array and maintain a hash map where keys are group sizes and values are lists of indices currently forming that group. Add each index to its corresponding list. When the list size equals the required group size, push it into the final result and clear the bucket. Every index is handled once, giving O(n) time.
What is the best approach for Group the People Given the Group Size They Belong To?
The most common solution uses a hash map that groups indices by their required group size. While iterating through the array, append each person to a bucket for that size. Once the bucket reaches the required capacity, move it to the result and start a new group. This approach runs in O(n) time and O(n) space.
Is Group the People Given the Group Size They Belong To asked at Google/Amazon/Meta?
This problem represents a typical hash map grouping pattern frequently asked in interviews at companies like Amazon, Google, and Meta. Variants involving grouping elements based on constraints or counts appear regularly in coding interviews and online assessments.
What data structure is used in Group the People Given the Group Size They Belong To?
The main data structure is a hash map (dictionary) that maps a group size to a list of people currently forming that group. Dynamic arrays or lists store the indices of members. The final result is a list of groups, each represented as an array of indices.
What is the time complexity of Group the People Given the Group Size They Belong To?
The optimal solution runs in O(n) time because each person is processed exactly once and added to a group once. Hash map insertions and lookups are constant time on average. The space complexity is O(n) since the result and temporary grouping structure store all indices.

Ready to solve this problem?

Practice Group the People Given the Group Size They Belong To with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Groups With Increasing Length

Next

Rabbits in Forest