Sort Items by Groups Respecting Dependencies
hard · verified · 65.6% accepted · 1,906 likes · top 70%
depth-first search · breadth-first search · graph theory · topological sort
Description
There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.
Return a sorted list of the items such that:
- The items that belong to the same group are next to each other in the sorted list.
- There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).
Return any solution if there is more than one solution and return an empty list if there is no solution.
Example 1:
Example 2:
Solution