Course Schedule II

Problem Statement

You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

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

There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.

Return a valid ordering of courses you can take to finish all courses. If there are many valid answers, return any of them. If it’s not possible to finish all courses, return an empty array.

Example 1:

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

Explanation: We must ensure that course 0 is taken before course 1.

Example 2:

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

Explanation: It’s impossible to finish all courses.

Constraints:

• 1 <= numCourses <= 1000
• 0 <= prerequisites.length <= 1000
• All prerequisite pairs are unique.

You should aim for a solution with O(V + E) time and O(V + E) space, where V is the number of courses (nodes) and E is the number of prerequisites (edges).

Recommended Time and Space Complexity

You should aim for a solution with O(V + E) time and O(V + E) space, where V is the number of courses (nodes) and E is the number of prerequisites (edges).

Hint 1

Consider the problem as a graph where courses represent the nodes, and prerequisites[i] = [a, b] represents a directed edge from a to b. We need to determine whether the graph contains a cycle. Why? Because if there is a cycle, it is impossible to complete the courses involved in the cycle. Can you think of an algorithm to detect a cycle in a graph and also find the valid ordering if a cycle doesn’t exist?

Hint 2

We can use DFS to detect a cycle in a graph. However, we also need to find the valid ordering of the courses, which can also be achieved using DFS. Alternatively, we can use the Topological Sort algorithm to find the valid ordering in this directed graph, where the graph must be acyclic to complete all the courses, and the prerequisite of a course acts as the parent node of that course. How would you implement this?

Hint 3

We compute the in-degrees of all the nodes. Then, we perform a BFS starting from the nodes that have no parents (indegree[node] == 0). At each level, we traverse these nodes, decrement the in-degree of their child nodes, and append those child nodes to the queue if their in-degree becomes 0. We only append nodes whose in-degree is 0 or becomes 0 during the BFS to our result array. If the length of the result array is not equal to the number of courses, we return an empty array.

Solution

Cycle Detection (DFS)

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """
    Finds a valid ordering of courses to take to finish all courses.

    Args:
        num_courses: The total number of courses.
        prerequisites: A list of prerequisites, where prerequisites[i] = [a, b] indicates
            that you must take course b first if you want to take course a.

    Returns:
        A valid ordering of courses, or an empty list if it's not possible to finish all courses.
    """
    prereq = {c: [] for c in range(num_courses)}
    for crs, pre in prerequisites:
        prereq[crs].append(pre)

    output = []
    visit, cycle = set(), set()

    def dfs(crs):
        if crs in cycle:
            return False
        if crs in visit:
            return True

        cycle.add(crs)
        for pre in prereq[crs]:
            if not dfs(pre):
                return False
        cycle.remove(crs)
        visit.add(crs)
        output.append(crs)
        return True

    for c in range(num_courses):
        if not dfs(c):
            return []
    return output

Time complexity: O(V + E) Space complexity: O(V + E)