Leetcode problem 64 - Group the People Given the Group Size They Belong To

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]]

/**
 * @param {number[]} groupSizes
 * @return {number[][]}
 */
var groupThePeople = function (groupSizes) {
  // create a map
  let map = {};
  // create a result array
  let result = [];
  // loop through the groupSizes
  for (let i = 0; i < groupSizes.length; i++) {
    // if the map doesn't have the group size
    if (!map[groupSizes[i]]) {
      // add the group size to the map
      map[groupSizes[i]] = [];
    }
    // push the index to the map
    map[groupSizes[i]].push(i);

    // if the map has the group size and the length of the group size is equal to the group size
    if (map[groupSizes[i]].length === groupSizes[i]) {
      // push the group size to the result
      result.push([...map[groupSizes[i]]]);
      // reset the map
      map[groupSizes[i]] = [];
    }
  }
  // return the result
  return result;
};

The time complexity is O(n), where n is the length of the groupSizes array. The code iterates through the input array, checks and updates the groups in constant time, and builds the result array when a group is complete.