LC 210 - Course Schedule II

Question

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.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1] **Explanation:** There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

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].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

Links

Question here and solution here

Solution

concept

This question is an extension of [[207. Course Schedule]] where we have to return the order itself instead of True/False. This question is an introduction of topological sort where we need to run DFS on each node and keep track of:

1. visited set, this set tracks the path of the current DFS, and it is used to detect cycles
2. seen set, this set is used keep track which node has been processed in the topological sort (i.e. the node has been added to the final answer) We will add the node once we have processed ALL pre-requisties (i.e. all the pre-req for this node has been added into the final answer).

The key difference with [[207. Course Schedule]] solution is that we do not use the early stopping code (comment out below):

if pre_req[course] == []:
    return True

• In Course Schedule I, this is fine: if no prerequisites, return True.
• In Course Schedule II, this is wrong because you never add such a course into ans.
  → That means nodes with no dependencies don’t get pushed into the final ordering. So your result will be incomplete.

  pre_req[course] = []
  

• In 207, this optimization is safe: once a course is processed, you can “clear” its prerequisites to avoid recomputation.
• In 210, this is wrong because it destroys the graph structure while DFS is still running on other nodes.
  Topological order requires every prerequisite edge to remain intact until the recursion finishes building ans. By erasing prerequisites prematurely, you may cause some valid dependencies to be skipped and the order to be incorrect.

In short:

• You keep the DFS visiting stack (visited) to detect cycles.
• You keep seen to avoid reprocessing nodes.
• You only add a course to ans after all its prerequisites are processed.
• That’s the standard post-order DFS topological sort, which gives a correct order when reversed (though in your case you don’t need to reverse since you append after recursion).

Note that in this question, since we cannot use the shortcut of pre_req[course]=[] to skip processed node, we used a seen set to skip.

Note that we can get rid of processed set and just check ans list but the solution will still works. But checking element in a set is O(1) but O(n) in list, so using set is much faster.

code

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        pre_req = {i: [] for i in range(numCourses)}
        for course, prereq in prerequisites:
            pre_req[course].append(prereq)
        
        visited = set() # current path, will be dynamically modified
        # we can get reid of processed and just check ans
        processed = set() # the node that has been processed in the topological sort. i.e. added into ans
        ans = []

        def dfs(course):
            if course in visited:
                return False # detected cycle
            if course in processed: # you can check ans here
                return True
            # this does not work, but works in Course Schedule I
            # if pre_req[course] == []:
            #     return True
            
            visited.add(course)
            for _course in pre_req[course]:
                if not dfs(_course): return False
            visited.remove(course)
            processed.add(course) # get rid this if just check ans
            ans.append(course)
            # this does not work, but works in Course Schedule I
            # pre_req[course] = []
            return True
        
        for course in range(numCourses):
            if not dfs(course): return []

        return ans

Complexity

time: $O(V + E)$
space: $O(V + E)$