Difficulty: Medium

This problem is a more complete version of the Course Schedule I problem. Topological Sort is used for sorting dependencies, in this problem we have to order courses in a way which we can take them all, and so courses have prerequisites and the prerequisites have prerequisites. This takes the form of a directed acyclic graph.

The input is an array of [course, prerequisite], so we have to first build an adjacency list since one course can have multiple prerequisites. We also have to check for loops in this graph, since it is possible that course A is a prerequisite for course B, and course B is a prerequisite for course A. So completing all courses would be impossible and so we return [].

There are two approaches to topological sort: DFS and BFS (Khan’s Algorithm)

Depth First Search Approach

This approach is one that first comes to mind.

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Time: O(n + e), Space: O(n + e) where n is the num of nodes and e is the num of edges
        prereq = {c: [] for c in range(numCourses)}
        for crs, pre in prerequisites:
            prereq[crs].append(pre)

        output = []
        visit, cycle = set(), set()

        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True

            cycle.add(crs)
            for pre in prereq[crs]:
                if dfs(pre) == False:
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True

        for c in range(numCourses):
            if dfs(c) == False:
                return []
        return output

We first start by building an adjacency list. We also need to make sure that courses that have no prerequisite and are not prerequisites to any other course are added since these courses would not be in the array and are essentially single nodes. This is why the numCourses input is important. So we make an adjacency list for all the nodes, even if it had no prerequisite, this way we cleanly avoid KeyError when looking through the children of the node.

Here, we can start from any node, and once all its children have been explored we add that to the order. While solving this problem I was under the misconception, that we need to figure out what node to start from, however, this makes us run into issues like detecting nodes with no start node since it’s a loop. Then we don’t detect the loop, and so we would have to check the length of the order, and it overall also costs us extra O(n) space. If we just dfs through all the nodes, and because we have the seen variable, no matter what node we start from we will get the correct order, and this makes our code much easier to understand.

We also need to keep track of the values already in order, so we need a seen set to check if a course is already in order in constant time. We also need to check what courses are in the current dfs path, so we use another set path. This way no nodes are visited more than once which betters our time complexity. The path set allows us to detect loops, if we run into a loop hasLoop[0] is set to True, and when the recursion ends an empty array is returned.

Khan’s Algorithms – Breath First Search Approach

The intuition behind this is pretty easy to understand, we simply keep removing the courses with no prerequisites (the leaves of the graph) until there are no courses left. This also handles loops pretty well, since a node that is part of a loop would have prerequisites that cannot be removed, so this ends the bfs iteration. Then we can just check if all the nodes are in the order and return [] if they are not. Isolated notes are handled well since they have 0 prerequisites, to begin with.

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Time: O(n + e), Space: O(n + e) where n is the num of nodes and e is the num of edges
        adjMap = {course: [] for course in range(numCourses)}
        inDegree = [0] * numCourses
        for course, preq in prerequisites:
            adjMap[preq].append(course)
            inDegree[course] += 1
        
        q = deque([])
        for course in range(numCourses):
            if inDegree[course] == 0:
                q.append(course)
        
        order = []
        while q:
            course = q.popleft()
            order.append(course)
            for c in adjMap[course]:
                inDegree[c] -= 1
                if inDegree[c] == 0:
                    q.append(c)
        
        return order if len(order) == numCourses else []

We need an inDegree array to keep track of how many prerequisites a node has, and the adjMap is now in reverse, so pretty much we can visualize this as flipping the arrows in the graph. This reverse adjMap allows us to start from the leaves and go upward. Every time we reach a course, we reduce its inDegree by 1, and if the inDegree is 0 we can add it to the queue.