210.Course_Schedule_II(Medium).md

210. Course Schedule II (Medium)

Date and Time: Aug 10, 2024, 22:44 (EST)

Link: https://leetcode.com/problems/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] = [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 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 <= a_i, b_i < numCourses

• a_i != b_i

• All the pairs [a_i, b_i] are distinct.

Walk-through:

1. We need to build "graph", which to add all the prereqs of a course into dictionary, prereq = {course: [prerequisites]}.

2. Run DFS to detect loop with cycle(), visited(), cycle is a temporary set to save courses from one course to all its prerequisites. So, we check the base case if node in cycle: return False, which means we have a loop in current course's prerequisites. if node in visited, we should return True, because we know this prereq can be finished.

3. We run DFS to check each course can be finished or not, if not dfs(crs), we should return [].

Python Solution:

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. Build prereq: {0: [], 1: [0], 2: [0], 3: [1, 2]}
        # 2. Run DFS on numCourses-1 with visited() and cycle(), check all prereq of current course.
        # If a crs in cycle: return False. If a crs in visited(): return True, then remove crs from cycle. Run cycle for a list of prerequistes.

        # TC: O(V+E), n = numCourses, SC: O(V)
        prereq = collections.defaultdict(list)      # {course: [prereq]}
        # Add prereq for each course
        for crs, pre in prerequisites:
            prereq[crs].append(pre)
        # Find the courses we need to take in order and detect loop
        cycle, visited = set(), set()
        ans = []    # order to take courses
        def dfs(node):
            if node in cycle:
                return False
            if node in visited:
                return True
            cycle.add(node)
            # Explore prereqs for current node
            for pre in prereq[node]:
                if not dfs(pre):
                    return False
            cycle.remove(node)
            visited.add(node)
            ans.append(node)
            return True
        # Check for every course, make sure no loop
        for crs in range(numCourses):
            # If there is a loop, return []
            if not dfs(crs):
                return []
        return ans

Time Complexity: $O(V + E)$, we are checking edges and vertices.
Space Complexity: $O(V + E)$, preMap{} is storing all edges and vertices.