Leetcode 1203 : Sort Items by Groups Respecting Dependencies

This question is a typical topology sort question. It applies two restrictions on the result:

1. the order of the items
2. the items in the same group must be adjacent to each other

If we decompose the first restriction into two parts, it becomes

• the order of the items in the same group
• the order of the items in the different group

Based on the second restriction, we must put the items in the same group together. If item A is in group C, item B is in group D, and item A comes before item B, it means group C comes before group D. The two restrictions can further be reinterpreted as:

1. the order of the items in the same group
2. the order of the groups

It breaks down into two topology sorts. The first sort figures out the order of the items in the same group and the second sort figures out the order of the groups. Then we concentrate all the groups together and get the final result.

There is a small problem with the items that have no group. It can be solved by assigning all of them a unique group id so that they can be consider a group with only one item.

Here is the link to my C++ implementation. Beat 98.4% on runtime and 100.0% on memory usage.