Sort Items By Group

Approach:

The approach is to use Topological Sorting to find the required sorted order of groups and also the required sorted order of items within each group. We can assume that each item that does not belong to any group is a part of a new group. Then we can use Topological Sort to sort the groups first. Then we can sort the items within each group. While using Topological Sorting, if we find a cycle in the graph, then we can safely say that there can never be an order of items that can match all the requirements and we can simply print “-1”. 

Steps:

1. Run a loop from i=0 to i<numOfItems, and do:
   1. If the ith item does not belong to any group we make group[i] = numOfGroups, and increase numOfGroups by 1.
2. Create a vector, say groupDependency of size numOfGroups to store the group dependencies.
3. Run a loop from i=0 to i<numOfItems, and do:
   1. For each item j in before[i], 
      1. If group[i] == group[j], continue. This is because if the groups of both these items are the same, then we don't have to consider that because order of items in a group doesn't matter
      2. Push group[j] in groupDependency[group[i]].
4. Initialize a variable, say cyclePresent = false. This will keep track of cycle in the graph.
5. Declare a vector, say itemsSort to store the sorting result of topSort(numOfItems, before, cyclePresent).
6. Declare a vector, say groupsSort to store the sorting result of topSort(numOfGroups, groupDependency, cyclePresent).
7. If cyclePresent = true, that means that there is a cycle present in this graph and thus there can not be any order of items that matches all the requirements so we create a vector containing a single integer “-1” and return it.
8. Now, define a Lambda function. A Lambda function allows us to write inline functions by accessing variables from the surrounding scope. Our Lambda function will sort items in the following way:
   1. If two items have the same group, then the item appearing first in itemsSort comes first.
   2. If the groups are different, then the item which belongs to the first appearing group in groupsSort comes first.
9. Now, create a vector, say sortedItems, of size numOfItems. Run a loop from i=0 to i<numOfItems and make sortedItems[i] = i.
10. Now Sort these items according to the lambda function
11. The sortedItems contains all the items in the required sorted order. So, we can simply return this vector.
     

vector<int> topSort(num, edges, cyclePresent) {

1. Define a boolean vector, say visited, of size num, and initialize all elements as false. This vector will keep track of all the nodes that have been visited already.
2. Define a boolean vector, say inCurrentCycle, of size num, and initialize all elements as false. This vector will keep track of all the nodes that are a part of the current cycle.
3. Initialize a variable, say order=0, to mark the order of the current cycle.
4. Define a vector, say sortedOrder, of size num, to store elements in the sorted order.
5. Run a loop from i=0 to i<num and do:
   1. If cyclePresent, return an empty vector.
   2. If ith element has not been visited, then call findOrder(i, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent).
6. Return sortedOrder.  

Void findOrder(i, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent) {

1. If the current node is a part of the current cycle, make cyclePresent as true and return. If the current node has been already visited, then simply return.
2. Now, make visited[i]=true and make inCurrentCycle[i] = true.
3. For every j in edges[i], do:
   1. If cyclePresent, return.
   2. Recursively call findOrder(j, order, sortedOrder, visited, inCurrentCycle, edges, cyclePresent).
4. Now, since we have completely traversed the current cycle, so the current node is not a part of the new cycle that we will traverse next. Hence, make inCurrentCycle[i]=false.
5. Make sortedOrder[i] = order. This is because all the elements of the current cycle have been given the same order.
6. Increase the order by 1 for the next cycle.

O(M + N), where N is the number of items and M is the number of groups.

We are going through the entire string and checking each character only once. This takes linear time.

O(M + N), where N is the number of items and M is the number of groups.

We need extra linear space to maintain the required sorted order of groups and also the required sorted order of the items within every group.