207.Course_Schedule_(Medium).md

207. Course Schedule (Medium)

Date and Time: Jun 2, 2024, 4:34 AM (EST)

Link: https://leetcode.com/problems/course-schedule/

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] = [a_i, b_i] indicates that you must take course $b_i$ first if you want to take course $a_i$.

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

Return true if you can finish all courses. Otherwise, return false.

Example 1:

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

Output: true

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2:

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

Output: false

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

KeyPoints:

1. Map every course's prerequisites from prerequisites.

2. Start checking every course by dfs to detect if loop exists or not. We add course to visited() and run dfs on this course's all prerequisites from the preMap, if this course's all prerequisites are all clear, we remove course from visited() and set the preMap[course] = [], which means this course can be completed.

My Solution:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. Build a map for all the prereqs with course
        # 2. Run DFS on the map, visited(), return False if a course in visited()

        # TC: O(V + E), SC: O(V + E)
        preMap = collections.defaultdict(list)
        for crs, pre in prerequisites:
            preMap[crs].append(pre)
        
        visited = set()
        def dfs(crs):
            if crs in visited:
                return False
            if preMap[crs] == []:
                return True
            visited.add(crs)
            # Run dfs on all prereqs of crs
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False
            # If a crs can be taken, we remove from visited and set preMap=[]
            visited.remove(crs)
            preMap[crs] = []
            return True

        # Check if every course can be taken
        for crs in range(numCourses):
            if not dfs(crs):
                return False
        return True

Time Complexity: $O(V + E)$, we traverse each node with their neighbors, so we traverse the graph of $O(V + E)$.
Space Complexity: $O(V + E)$, we build the graph $O(V + E)$.