[Top Interview 150] 210. Course Schedule II

Solution)

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # preDict is a dict that saves {crs : [prerequiste courses]}
        preDict = {i:[] for i in range(numCourses)}

        # Fills up preDict according to the given prerequisites
        for crs, pre in prerequisites:
            preDict[crs].append(pre)

        # visit is a set of vertices that are added to res
        # path is a set of vertices that were visited along the current path
        # res is a list of order to take courses
        visit, path = set(), set()
        res = []

        def dfs(crs):
            # If the current crs is a part of a cycle, return False
            # If the current crs was added to res, return True
            if crs in path: return False
            if crs in visit: return True

            path.add(crs)

            # Run dfs() for all prerequisites of the current crs
            for pre in preDict[crs]:
                # If one of the prerequisites is not valid, return False
                if not dfs(pre): return False

            path.remove(crs)
            visit.add(crs)
            res.append(crs)
            
            # If the current crs is valid, return True
            return True
        
        for crs in range(numCourses):
            # If it's impossible to finish all courses, return []
            if not dfs(crs):
                return []
            
        return res

 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(E+V)
Space Complexity: O(E+V)
 

Explanation)

We'll use DFS to iterate a graph of courses. We'll indicate the graph by making a hashmap.
 
As we iterate, we'll check whether the graph contains a cycle and make a list of valid order to finish courses.
 

1. Initialization)

To work with a graph, we need an adjacency list using hashmap that maps courses to a list of prerequisites.
Variable preDict will be that hashmap.
 
Variable visit is a set of vertices that are added to res. This allows us to skip those vertices when iterated again.
Variable path is a set of vertices that were visited in a current path of DFS. If a vertice that was already visited in a path is seen again, we know that we're in a cycle.
 
Variable res is a list that will save a valid order of courses.
 

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. Initialization
        preDict = {i:[] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preDict[crs].append(pre)

        visit, path = set(), set()
        res = []

 

2. Base Case)

Now let's define a helper function that will help us DFS.
 
If the current crs is in path, that means crs was already visited while iterating the current path. This means that we're in a cycle, so it's impossible to finish the courses. Thus we must return an empty list. We'll return False for now.
 
If the current crs is in visit, that means crs is a course in res. If we know that crs is already verified, we don't need to waste running time by revisiting. 
 
There is no specific reason in returning True. We just return that boolean value because we don't want to return False.  
 
After checking the base cases, we add crs to path so that we don't fall into a cycle.
 

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. Initialization
        preDict = {i:[] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preDict[crs].append(pre)

        visit, path = set(), set()
        res = []

        def dfs(crs):
            # 2. Base Case
            if crs in path: return False
            if crs in visit: return True
            
            path.add(crs)

 

3. Recursive Calls)

Now let's run DFS. While we iterate a DFS path, we'll check if there's a cycle.
 
If we receive a False, it means there's a cycle.
 

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. Initialization
        preDict = {i:[] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preDict[crs].append(pre)

        visit, path = set(), set()
        res = []

        def dfs(crs):
            # 2. Base Case
            if crs in path: return False
            if crs in visit: return True

            path.add(crs)

            # 3. Recursive calls
            for pre in preDict[crs]:
                if not dfs(pre): return False

 

4. Update an array and sets)

After we're done with the for-loop, we know that the current crs is a valid vertice.
 
Now let's update some data that we're done with the current crs.
Remove crs from path because we'll not visit this crs in this path anymore.
Add crs to visit and append crs to res because this crs is a valid vertice.
 
Once all the updates are done, return True to break out of the function.
 

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. Initialization

        def dfs(crs):
            # 2. Base Case
            if crs in path: return False
            if crs in visit: return True

            path.add(crs)

            # 3. Recursive calls
            for pre in preDict[crs]:
                if not dfs(pre): return False

            # 4. Update an array and sets
            path.remove(crs)
            visit.add(crs)
            res.append(crs)
            
            return True

 

5. Run dfs() from 0 ~ numCourses-1)

Now run dfs() from 0 to numCourses-1. If False is returned from one of the calls, it means we found a cycle in the graph. Since it's impossible to finish the courses, return an empty list.
 
If False wasn't returned, it's possible to finish the courses so return res.
 

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. Initialization

        def dfs(crs):
            # 2. Base Case
            if crs in path: return False
            if crs in visit: return True

            path.add(crs)

            # 3. Recursive calls
            for pre in preDict[crs]:
                if not dfs(pre): return False

            # 4. Update an array and sets
            path.remove(crs)
            visit.add(crs)
            res.append(crs)
            
            return True
        
        # 5. Run dfs() from 0 ~ numCourses-1
        for crs in range(numCourses):
            if not dfs(crs):
                return []
        
        return res

---

 
 
I had some rough sketches of the solution, but I couldn't fill up the details. It's amazing how he can come up with these details.