Group the People Given the Group Size They Belong To solution and explanation
Google
9 more videos on this problem
Group the People Given the Group Size They Belong To | Dry Run | LYFT | Leetcode - 1282codestorywithMIK · 14:46 · 6K views
LeetCode 1282: Group the People Given the Group Size They Belong To - Interview Prep Ep 24Fisher Coder · 14:27 · 3K views
Leetcode Solution - 1282 Group the People Given the Group Size They Belong ToJohn Leonardo · 5:18 · 2K views
Leetcode 1282: Group the People Given the Group Size They Belong ToAlgorithms Casts · 13:38 · 1K views
LeetCode 1282. Group the People Given the Group Size They Belong To - Apple Interview QuestionCode with Carter · 7:35 · 870 views
LeetCode 1282 : C++ Solution | Group the People Given the Group Size They Belong ToAmit Manjarly · 20:28 · 797 views
Group the People Given the Group Size They Belong To | Easiest solution | Code #WithMe | LeetcodeCode feed · 7:10 · 738 views
Unlock the Power of Hash Tables LeetCode 1282. Group the People Given the Group Size They Belong TovanAmsen · 6:55 · 672 views
LeetCode 1282 : JAVA Solution | Group the People Given the Group Size They Belong ToAmit Manjarly · 24:15 · 655 views
Daily Leetcode #1259: Sep 11, 2023 - 1282. Group the People Given the Group Size They Belong ToProgramming Live with Larry · 9:23 · 316 views
The problem
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 == n1 <= n <= 5001 <= 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.
def group_the_people(groupSizes):
from collections import defaultdict
size_to_people = defaultdict(list)
result = []
for person, size in enumerate(groupSizes):
size_to_people[size].append(person)
if len(size_to_people[size]) == size:
result.append(size_to_people[size])
size_to_people[size] = []
return resultimport java.util.*;
public List<List<Integer>> groupThePeople(int[] groupSizes) {
Map<Integer, List<Integer>> sizeToPeople = new HashMap<>();
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < groupSizes.length; i++) {
int size = groupSizes[i];
sizeToPeople.putIfAbsent(size, new ArrayList<>());
sizeToPeople.get(size).add(i);
if (sizeToPeople.get(size).size() == size) {
result.add(new ArrayList<>(sizeToPeople.get(size)));
sizeToPeople.get(size).clear();
}
}
return result;
}#include <vector>
#include <unordered_map>
using namespace std;
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
unordered_map<int, vector<int>> size_to_people;
vector<vector<int>> result;
for (int i = 0; i < groupSizes.size(); ++i) {
int size = groupSizes[i];
size_to_people[size].push_back(i);
if (size_to_people[size].size() == size) {
result.push_back(size_to_people[size]);
size_to_people[size].clear();
}
}
return result;
}var groupThePeople = function(groupSizes) {
const sizeToPeople = new Map();
const result = [];
groupSizes.forEach((size, index) => {
if (!sizeToPeople.has(size)) {
sizeToPeople.set(size, []);
}
sizeToPeople.get(size).push(index);
if (sizeToPeople.get(size).length === size) {
result.push(sizeToPeople.get(size));
sizeToPeople.set(size, []);
}
});
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// A helper struct for mapping size with people's list
typedef struct {
int *people;
int size;
int capacity;
} Group;
int** groupThePeople(int* groupSizes, int groupSizesSize, int* returnSize, int** returnColumnSizes) {
int** result = malloc(sizeof(int*) * groupSizesSize);
*returnColumnSizes = malloc(sizeof(int) * groupSizesSize);
int resultIdx = 0;
Group* groups = malloc(sizeof(Group) * groupSizesSize);
for (int i = 0; i < groupSizesSize; ++i) {
groups[i].people = malloc(sizeof(int) * groupSizesSize);
groups[i].size = 0;
groups[i].capacity = 0;
}
for (int i = 0; i < groupSizesSize; ++i) {
int size = groupSizes[i];
groups[size].people[groups[size].size++] = i;
if (groups[size].size == size) {
result[resultIdx] = malloc(sizeof(int) * size);
for (int j = 0; j < size; ++j) {
result[resultIdx][j] = groups[size].people[j];
}
(*returnColumnSizes)[resultIdx] = size;
resultIdx++;
groups[size].size = 0;
}
}
free(groups);
*returnSize = resultIdx;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> GroupThePeople(int[] groupSizes) {
var sizeToPeople = new Dictionary<int, List<int>>();
var result = new List<IList<int>>();
for (int i = 0; i < groupSizes.Length; i++) {
int size = groupSizes[i];
if (!sizeToPeople.ContainsKey(size)) {
sizeToPeople[size] = new List<int>();
}
sizeToPeople[size].Add(i);
if (sizeToPeople[size].Count == size) {
result.Add(new List<int>(sizeToPeople[size]));
sizeToPeople[size].Clear();
}
}
return result;
}
}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.
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.
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.
def group_the_people(groupSizes):
groups, result = {}, []
for i, size in enumerate(groupSizes):
if size not in groups:
groups[size] = []
groups[size].append(i)
if len(groups[size]) == size:
result.append(groups[size])
del groups[size]
return resultimport java.util.*;
class Solution {
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> result = new ArrayList<>();
List<Integer>[] groups = new List[groupSizes.length + 1];
for (int i = 0; i < groupSizes.length; i++) {
int size = groupSizes[i];
if (groups[size] == null) groups[size] = new ArrayList<>();
groups[size].add(i);
if (groups[size].size() == size) {
result.add(groups[size]);
groups[size] = new ArrayList<>();
}
}
return result;
}
}#include <vector>
using namespace std;
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
vector<vector<int>> groups(groupSizes.size() + 1);
vector<vector<int>> result;
for (int i = 0; i < groupSizes.size(); i++) {
groups[groupSizes[i]].push_back(i);
if (groups[groupSizes[i]].size() == groupSizes[i]) {
result.emplace_back(move(groups[groupSizes[i]]));
groups[groupSizes[i]].clear();
}
}
return result;
}var groupThePeople = function(groupSizes) {
const groups = Array.from({length: groupSizes.length + 1}, () => []);
const result = [];
groupSizes.forEach((size, index) => {
groups[size].push(index);
if (groups[size].length === size) {
result.push(groups[size]);
groups[size] = [];
}
});
return result;
};#include <string.h>
#include <stdlib.h>
typedef struct {
int* people;
int count;
} Group;
int** groupThePeople(int* groupSizes, int groupSizesSize, int* returnSize, int** returnColumnSizes) {
Group* groups = malloc((groupSizesSize + 1) * sizeof(Group));
for (int i = 0; i <= groupSizesSize; i++) {
groups[i].people = malloc(groupSizesSize * sizeof(int));
groups[i].count = 0;
}
int** result = malloc(groupSizesSize * sizeof(int*));
*returnColumnSizes = malloc(groupSizesSize * sizeof(int));
int resultIndex = 0;
for (int i = 0; i < groupSizesSize; i++) {
int size = groupSizes[i];
groups[size].people[groups[size].count++] = i;
if (groups[size].count == size) {
result[resultIndex] = malloc(size * sizeof(int));
memcpy(result[resultIndex], groups[size].people, size * sizeof(int));
(*returnColumnSizes)[resultIndex] = size;
resultIndex++;
groups[size].count = 0;
}
}
free(groups);
*returnSize = resultIndex;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> GroupThePeople(int[] groupSizes) {
var result = new List<IList<int>>();
List<int>[] groups = new List<int>[groupSizes.Length + 1];
for (int i = 0; i < groupSizes.Length; i++) {
int size = groupSizes[i];
if (groups[size] == null) groups[size] = new List<int>();
groups[size].Add(i);
if (groups[size].Count == size) {
result.Add(new List<int>(groups[size]));
groups[size].Clear();
}
}
return result;
}
}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.
The time complexity is O(n), and similarly, space complexity is O(n) due to linear storage requirements.
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.
function groupThePeople(groupSizes: number[]): number[][] {
const n: number = groupSizes.length;
const g: number[][] = Array.from({ length: n + 1 }, () => []);
for (let i = 0; i < groupSizes.length; i++) {
const size: number = groupSizes[i];
g[size].push(i);
}
const ans: number[][] = [];
for (let i = 1; i <= n; i++) {
const group: number[] = [];
for (let j = 0; j < g[i].length; j += i) {
group.push(...g[i].slice(j, j + i));
ans.push([...group]);
group.length = 0;
}
}
return ans;
}func groupThePeople(groupSizes []int) [][]int {
n := len(groupSizes)
g := make([][]int, n+1)
for i, v := range groupSizes {
g[v] = append(g[v], i)
}
ans := [][]int{}
for i, v := range g {
for j := 0; j < len(v); j += i {
ans = append(ans, v[j:j+i])
}
}
return ans
}impl Solution {
pub fn group_the_people(group_sizes: Vec<i32>) -> Vec<Vec<i32>> {
let n: usize = group_sizes.len();
let mut g: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
for (i, &size) in group_sizes.iter().enumerate() {
g[size as usize].push(i);
}
let mut ans: Vec<Vec<i32>> = Vec::new();
for (i, v) in g.into_iter().enumerate() {
for j in (0..v.len()).step_by(i.max(1)) {
ans.push(
v[j..(j + i).min(v.len())]
.iter()
.map(|&x| x as i32)
.collect(),
);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap-based Grouping | O(n) | O(n) | Best general solution. Simple grouping using hash buckets for each required size. |
| Index-Based Direct Group Allocation | O(n) | O(n) | When you want fewer map operations and straightforward index tracking. |
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.