loading...
Cover image for Algorithms Problem Solving: Group the people

Algorithms Problem Solving: Group the people

teekay profile image TK Originally published at leandrotk.github.io ・3 min read

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Group the People problem. The description looks like this:

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Examples

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Solution

My first idea was to just group the sizes into a hash map where the key is the size and the value is a list of all the indices for a specific size. An example would be to transform this list:

[3, 3, 1, 2, 3, 2, 3, 3, 3]

...into this hash map:

{
    1: [2],
    2: [3, 5],
    3: [0, 1, 4, 6, 7, 8]
}

The code is very simple. You start an empty hash map and then populate while iterating the list:

grouped_by_size = {}

for index in range(len(group_sizes)):
    size = group_sizes[index]

    if size in grouped_by_size:
        grouped_by_size[size] += [index]
    else:
        grouped_by_size[size] = [index]

With this organized data, we just need to group them by the id.

We will go from this:

{
    1: [2],
    2: [3, 5],
    3: [0, 1, 4, 6, 7, 8]
}

To this:

[[2], [3, 5], [0, 1, 4], [6, 7, 8]]

The idea here is to create an empty list to add all indices. Then iterate through the hash map and for each key-value, we add the value to the list. But we need to consider that our lists can be greater the maximum permitted length. So we cut them by the maximum length.

grouped_by_ids = []

for size, indices in grouped_by_size.items():
    for index in range(0, len(indices), size):
        grouped_by_ids.append(indices[index:index+size])

return grouped_by_ids

Now we have the grouped_by_ids list with all indices.

The whole algorithm looks like this:

def group_the_people(group_sizes):
    grouped_by_size = {}

    for index in range(len(group_sizes)):
        size = group_sizes[index]

        if size in grouped_by_size:
            grouped_by_size[size] += [index]
        else:
            grouped_by_size[size] = [index]

    grouped_by_ids = []

    for size, indices in grouped_by_size.items():
        for index in range(0, len(indices), size):
            grouped_by_ids.append(indices[index:index+size])

    return grouped_by_ids

Resources

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

Posted on Jun 3 by:

teekay profile

TK

@teekay

Sharing knowledge https://leandrotk.github.io/tk

Discussion

markdown guide
 

I could use a nifty one-line to convert grouped_by_size dict to grouped_by_ids list like this: [*grouped_by_size.values()]. It's in the order of the grouped_by_size keys.