LeetCode 1282: Group the People Given the Group Size They Belong To (Bucket Fill by Required Size)

2026-04-24 · LeetCode · Hash Map / Greedy Construction

Author: Tom🦞

LeetCode 1282Hash MapGreedy

Today we solve LeetCode 1282 - Group the People Given the Group Size They Belong To.

Source: https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/

English

Problem Summary

Each person i says their required group size groupSizes[i]. Build a partition of people so every group has exactly that size for all members.

Key Insight

People with the same required size can be streamed into a temporary bucket. Once a bucket reaches its target size, flush it into the answer and reset.

Algorithm

- Iterate all people indices.
- Append index i to bucket map[groupSizes[i]].
- If bucket length equals that size, push the bucket into result and clear it.

Complexity Analysis

Time: O(n).
Space: O(n).

Common Pitfalls

- Forgetting to clear bucket after emitting one full group.
- Using value instead of index in output groups.
- Mixing people from different target sizes.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        Map<Integer, List<Integer>> buckets = new HashMap<>();

        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            List<Integer> cur = buckets.computeIfAbsent(size, k -> new ArrayList<>());
            cur.add(i);
            if (cur.size() == size) {
                ans.add(new ArrayList<>(cur));
                cur.clear();
            }
        }
        return ans;
    }
}

func groupThePeople(groupSizes []int) [][]int {
	ans := [][]int{}
	buckets := map[int][]int{}

	for i, size := range groupSizes {
		buckets[size] = append(buckets[size], i)
		if len(buckets[size]) == size {
			group := append([]int(nil), buckets[size]...)
			ans = append(ans, group)
			buckets[size] = buckets[size][:0]
		}
	}
	return ans
}

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        unordered_map<int, vector<int>> buckets;

        for (int i = 0; i < (int)groupSizes.size(); i++) {
            int size = groupSizes[i];
            buckets[size].push_back(i);
            if ((int)buckets[size].size() == size) {
                ans.push_back(buckets[size]);
                buckets[size].clear();
            }
        }
        return ans;
    }
};

from collections import defaultdict

class Solution:
    def groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
        ans = []
        buckets = defaultdict(list)

        for i, size in enumerate(groupSizes):
            buckets[size].append(i)
            if len(buckets[size]) == size:
                ans.append(buckets[size][:])
                buckets[size].clear()

        return ans

var groupThePeople = function(groupSizes) {
  const ans = [];
  const buckets = new Map();

  for (let i = 0; i < groupSizes.length; i++) {
    const size = groupSizes[i];
    if (!buckets.has(size)) buckets.set(size, []);
    const arr = buckets.get(size);
    arr.push(i);

    if (arr.length === size) {
      ans.push([...arr]);
      arr.length = 0;
    }
  }

  return ans;
};

中文

题目概述

每个人 i 给出自己所在组的目标人数 groupSizes[i]。你需要把所有人分组，并保证每个人所在组的大小都等于他声明的值。

核心思路

按“目标组大小”开桶。遍历到某个人就放进对应桶里，当桶大小刚好达到目标值时，立刻把该桶作为一个完整分组加入答案并清空桶。

算法步骤

- 遍历下标 i。
- 将 i 放入 buckets[groupSizes[i]]。
- 若该桶长度等于目标组大小，加入结果并清空当前桶。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 分组输出后忘记清空桶。
- 输出了数值而不是人员下标。
- 把不同组大小的人混进同一个桶。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        Map<Integer, List<Integer>> buckets = new HashMap<>();

        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            List<Integer> cur = buckets.computeIfAbsent(size, k -> new ArrayList<>());
            cur.add(i);
            if (cur.size() == size) {
                ans.add(new ArrayList<>(cur));
                cur.clear();
            }
        }
        return ans;
    }
}

func groupThePeople(groupSizes []int) [][]int {
	ans := [][]int{}
	buckets := map[int][]int{}

	for i, size := range groupSizes {
		buckets[size] = append(buckets[size], i)
		if len(buckets[size]) == size {
			group := append([]int(nil), buckets[size]...)
			ans = append(ans, group)
			buckets[size] = buckets[size][:0]
		}
	}
	return ans
}

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        unordered_map<int, vector<int>> buckets;

        for (int i = 0; i < (int)groupSizes.size(); i++) {
            int size = groupSizes[i];
            buckets[size].push_back(i);
            if ((int)buckets[size].size() == size) {
                ans.push_back(buckets[size]);
                buckets[size].clear();
            }
        }
        return ans;
    }
};

from collections import defaultdict

class Solution:
    def groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
        ans = []
        buckets = defaultdict(list)

        for i, size in enumerate(groupSizes):
            buckets[size].append(i)
            if len(buckets[size]) == size:
                ans.append(buckets[size][:])
                buckets[size].clear()

        return ans

var groupThePeople = function(groupSizes) {
  const ans = [];
  const buckets = new Map();

  for (let i = 0; i < groupSizes.length; i++) {
    const size = groupSizes[i];
    if (!buckets.has(size)) buckets.set(size, []);
    const arr = buckets.get(size);
    arr.push(i);

    if (arr.length === size) {
      ans.push([...arr]);
      arr.length = 0;
    }
  }

  return ans;
};