Skip to content

1282. Group the People Given the Group Size They Belong To 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
    vector<vector<int>> ans;
    unordered_map<int, vector<int>> groupSizeToIndices;

    for (int i = 0; i < groupSizes.size(); ++i)
      groupSizeToIndices[groupSizes[i]].push_back(i);

    for (const auto& [groupSize, indices] : groupSizeToIndices) {
      vector<int> groupIndices;
      for (const int index : indices) {
        groupIndices.push_back(index);
        if (groupIndices.size() == groupSize) {
          ans.push_back(groupIndices);
          groupIndices.clear();
        }
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public List<List<Integer>> groupThePeople(int[] groupSizes) {
    List<List<Integer>> ans = new ArrayList<>();
    Map<Integer, List<Integer>> groupSizeToIndices = new HashMap<>();

    for (int i = 0; i < groupSizes.length; ++i) {
      final int groupSize = groupSizes[i];
      groupSizeToIndices.putIfAbsent(groupSize, new ArrayList<>());
      groupSizeToIndices.get(groupSize).add(i);
    }

    for (Map.Entry<Integer, List<Integer>> entry : groupSizeToIndices.entrySet()) {
      final int groupSize = entry.getKey();
      List<Integer> indices = entry.getValue();
      List<Integer> groupIndices = new ArrayList<>();
      for (final int index : indices) {
        groupIndices.add(index);
        if (groupIndices.size() == groupSize) {
          ans.add(new ArrayList<>(groupIndices));
          groupIndices.clear();
        }
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
    ans = []
    groupSizeToIndices = defaultdict(list)

    for i, groupSize in enumerate(groupSizes):
      groupSizeToIndices[groupSize].append(i)

    for groupSize, indices in groupSizeToIndices.items():
      groupIndices = []
      for index in indices:
        groupIndices.append(index)
        if len(groupIndices) == groupSize:
          ans.append(groupIndices.copy())
          groupIndices.clear()

    return ans