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.

Python

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)$.

Java

class Solution {
    /* 
    crs_map: {crs: [prerequisites]}
    Run DFS on crs to check if there is any cycle in crs's prerequisites
    TC: O(V+E), SC: O(V+E)
    */
    private Map<Integer, List<Integer>> crsMap = new HashMap<>();
    private Set<Integer> cycle = new HashSet<>();

    private boolean dfs(int crs) {
        // Check if we have cycle
        if (cycle.contains(crs)) {
            return false;
        }
        // Check if this course can be finished
        if (!crsMap.containsKey(crs) || crsMap.get(crs).isEmpty()) {
            return true;
        }
        cycle.add(crs);
        // Check crs prerequisites
        for (int nei: crsMap.get(crs)) {
            if (!dfs(nei)) {
                return false;
            }
        }
        // Remove crs from cycle and clear crs prerequisites in crsMap
        cycle.remove(crs);
        crsMap.get(crs).clear();
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Fill in crsMap
        for (int i = 0; i < prerequisites.length; i++) {
            int crs = prerequisites[i][0];
            int pre = prerequisites[i][1];
            // Make sure to create list before adding
            crsMap.putIfAbsent(crs, new ArrayList<>());
            crsMap.get(crs).add(pre);
        }

        // Check each course
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i)) {
                return false;
            }
        }
        return true;
    }
}