[Top Interview 150] 207. Course Schedule

Solution)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # preMap will save {course : [prerequisites]}
        # visitSet will save courses that were visited while DFS
        preMap, visitSet = collections.defaultdict(list), set()
        
        # Set up preMap according to the given prerequisites
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        # Helper function that will depth-first-search
        def dfs(crs):
            # 2 base cases
            if crs in visitSet:
                return False
            if preMap[crs] == []:
                return True

            # Allows us to check if the current course has been
            # already visited. If it's already visited, 
            # that means the graph is a cycle
            visitSet.add(crs)

            # Code that runs DFS. If a false is returned in a stack
            # of DFS calls, it'll recursively return False all the way 
            # up to the first call. That'll return False in the end.  
            for pre in preMap[crs]:
                if not dfs(pre): return False

            # Make sure to update your visitSet after checking that
            # the current crs is a good node w/out a cycle. Also,
            # it's a process of reverting visitSet to an empty set.
            visitSet.remove(crs)
            
            # Also make preMap[crs] = [] so that we save time not
            # repeating the same DFS calls.
            preMap[crs] = []
            
            return True

        # Run dfs for 0~numCourses-1 indexes
        for crs in range(numCourses):
            # If one of the crs happens to be a cycle
            # immediately return False
            if not dfs(crs): return False
        
        # If all crs passed, return True
        return True

 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n+p)
Space Complexity: O(p)
* n = numCourses, p = len(prerequisites)
 

Explanation)

We'll use DFS to iterate the graph and check whether there is a cycle.
 
To do that, we'll have a hashmap that will map a course to a list of prerequisites. Using this a graph, we'll DFS until the current vertice is the last vertice. If there is a cycle in a graph, we'll return False.
 
We'll run dfs from 0 to numCourses-1.
 

1. Initialization)

As explained above, we need a hashmap for us to work with as a graph.
Variable preMap will be a default dictionary of empty lists.
 
While DFS, we need a way to check if there is a cycle. We can check this using a set.
Variable visitSet will save nodes while DFS. As we DFS, we'll check if the current node has been already visited.
 
Iterate prerequisites to fill preMap.
 

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. Initialization
        preMap, visitSet = collections.defaultdict(list), set()
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

 

2. Base Cases)

Now let's define a function that will dfs the graph(hashmap).
 
As usual for recursive functions, we have base cases.
1) If the current node(course) has already been visited, it means we're in a cycle so return False.
2) If the current node doesn't have a prerequisite, that means we've reached the last node of a path so return True.
 
Say the path is
root -> ... -> crs.
 
And if crs is the last node, the current path is a valid path so we return True and will look for other paths. 
 

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. Initialization
        preMap, visitSet = collections.defaultdict(list), set()
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        def dfs(crs):
            # 2. base cases
            if crs in visitSet:
                return False
            if preMap[crs] == []:
                return True

 

3. Add crs to visitSet)

If the current crs didn't fall into the base cases, we need to dive deeper.
 
Before we move on to deeper nodes, we have to add crs to visitSet. This prevents us from entering a cycle while traversing down.
 

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. Initialization
        preMap, visitSet = collections.defaultdict(list), set()
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        def dfs(crs):
            # 2. base cases
            if crs in visitSet:
                return False
            if preMap[crs] == []:
                return True

            # 3. Add crs to visitSet
            visitSet.add(crs)

 

4. DFS from the current crs)

Now that we added crs to visitSet, let's keep traversing down.
 
Keep in mind that there might be multiple prerequisites for a certain course. We need to DFS for all the prerequisites.
 
While DFS, if we find a cycle (meaning the returned result of dfs() is False), we'll return False. If we get False from one of the recursive calls, the entire stack will eventually return False in the end.
 

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

        def dfs(crs):
            # 2. base cases
            if crs in visitSet:
                return False
            if preMap[crs] == []:
                return True

            # 3. Add crs to visitSet
            visitSet.add(crs)

            # 4. DFS from the current crs 
            for pre in preMap[crs]:
                if not dfs(pre): return False

 

5. Update visitSet & preMap)

Think Step 4 as a scanner that verifies the current node is a valid node to keep. At this point we know the current node is a valid node.
 
When we exit the for loop, it means the current path is a valid path which means the current node is a valid node. Thus we'll update visitSet by removing the current node(crs).
 
Also, since we know that the current node is a safe node, we'll update preMap so that the current node's list contains 0 prerequisite. This allows us to DFS faster when we traverse other paths.
 
After all the udpates are completed, return True as the current node is a valid node.
 

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

        def dfs(crs):
            # 2. base cases
            if crs in visitSet:
                return False
            if preMap[crs] == []:
                return True

            # 3. Add crs to visitSet
            visitSet.add(crs)

            # 4. DFS from the current crs 
            for pre in preMap[crs]:
                if not dfs(pre): return False

            # 5. Update visitSet & preMap
            visitSet.remove(crs)
            preMap[crs] = []
            
            return True

 

6. Run dfs() from 0 to numCourses-1)

Now it's time to actually run dfs().
 
We'll run dfs() starting from 0 to numCourses-1. If we find that there is a cycle while DFS it' return False. If False is returned we know the given courses are impossible to finish, so we'll return False.
 
If we didn't find a cycle, False will not be returned from dfs() in the for-loop. Then return True.
 

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

        def dfs(crs):
            # 2. base cases

            # 3. Add crs to visitSet

            # 4. DFS from the current crs 

            # 5. Update visitSet & preMap

        # 6. Run dfs() from 0 to numCourses-1
        for crs in range(numCourses):
            if not dfs(crs): return False
        return True

---

 
 
It's really annoying to keep looking at other solutions, but I'm learning a lot from it. It is what it is and I'll try my best to learn as much as possible from these problems.