Daily Coding - Day 3

210. Course Schedule - II

There are a total of?numCourses?courses you have to take, labeled from?0?to?numCourses - 1. You are given an array?prerequisites?where?prerequisites[i] = [ai, bi]?indicates that you?must?take course?bi?first if you want to take course?ai.

• For example, the pair?[0, 1], indicates that to take course?0?you have to first take course?1.

Return?the ordering of courses you should take to finish all courses. If there are many valid answers, return?any?of them. If it is impossible to finish all courses, return?an empty array.

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].        

The questions which deal with "dependencies" are often solved through the Kahn's Algorithm for Topological Sort. The algorithm ensures that for every directed edge UV, u comes before v in the sorted array. The algorithm consists of the following steps:

1. Preparation of an adjacency list, which is a map, where each key is a source, and has a list of destinations dependent on it, stored as value.
2. Calculation of indegrees of each vertex.
3. Push all the nodes with 0 indegrees i.e. the nodes which are independent, and can act potential starting points, to a queue which can be processed in a Breadth First Search manner.

1. Starting processing the queue, and everytime you poll an element from queue, push it to the resultant array and reduce the indegrees of each of the dependent nodes, and push such nodes which now have 0 indegrees to the queue. These are the nodes that can now be visited as we have already covered the dependencies required to visit them
2. It is possible that you cannot process all nodes, this is the case in case of a cyclical graph. In that case your resultant array will have lesser elements than the total number of nodes.

Full Code can be found here.