Group By Size

I worked on a fun LeetCode problem earlier this week and wanted to discuss the problem here.

The problem is called 'Group the People Given the Group Size They Belong To'.

The problem tells us that there should be a function that accepts an array of integers that represent the size of group that each element belongs to. We are asked to return one example of an acceptable grouping (with each element in the output represented by the index in the original array). For example:

An input of [1, 2, 4, 2, 4, 4, 4] could return [[0], [1, 3], [2, 4, 5, 6]. This is an acceptable return because when examining the input, index 0 is in a group of 1 so it should be grouped alone. Indexes 1 and 3 are both in a group of 2, and indexes 2, 4, 5 and 6 are all in a group of 4. This example was straightforward because there were not multiple groups of the same size. If we received an input of [2, 2, 2, 2, 2, 2, 2, 2] then you could return any combination of four pairs of indexes.

Here is my solution:

function groupThePeople(groupSizes) {
let groups = {};
let result = [];
for (let i = 0; i < groupSizes.length; i++) {
let tar = groupSizes[i];
if (tar === 1) {
result.push([i]);
continue;
}
if (!groups[tar]) {
groups[tar] = [];
groups[tar].push(i);
} else {
groups[tar].push(i);
if (groups[tar].length === tar) {
result.push(groups[tar]);
groups[tar] = [];
}
}
}
return result;
}


I went about solving this problem by utilizing an object to store groups as they are being filled. My logic was that if I created a key for each group size and used this object as a staging place, I could push a value array into my final result array once it was full. I then reset that object key to an empty array so that it would be ready for future indexes that also have the same group size.

My for loop iterates over each element of the input. If the element I am examining is 1, I know that I can immediately push the index into my result array and skip to the next index in my for loop.

The remaining code in my for loop carries out the logic to keep my staging object organized.

Once we exit the for loop I know that we have placed each index into an appropriate group, so we return the result array (this problem did guarantee that there would be at least one solution for each input, so I did not account for invalid inputs; if I did want it to notify of an invalid input I would flatten the result array before the return and confirm that it was the same length as the input array).\

This was one way of solving this problem but I'm sure there are many more!

Posted on by:

mzakzook

Code, food, travel and dogs. LA -> Oakland.