Course Schedule

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.

The pair [0, 1], indicates that must take course 1 before taking course 0.

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

Return true if it is possible to finish all courses, otherwise return false.

Example 1:

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


Output: true

Explanation: First take course 1 (no prerequisites) and then take course 0.

Example 2:

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


Output: false

Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.

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

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 prerequisite[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 cycle in a graph?

Hint 2

We can use the Depth First Search (DFS) algorithm to detect a cycle in a graph. We iterate over each course, run a DFS from that course, and first try to finish its prerequisite courses by recursively traversing through them. To detect a cycle, we initialize a hash set called path, which contains the nodes visited in the current DFS call. If we encounter a course that is already in the path, we can conclude that a cycle is detected. How would you implement it?

Hint 3

We run a DFS starting from each course by initializing a hash set, path, to track the nodes in the current DFS call. At each step of the DFS, we return false if the current node is already in the path, indicating a cycle. We recursively traverse the neighbors of the current node, and if any of the neighbor DFS calls detect a cycle, we immediately return false. Additionally, we clear the neighbors list of a node when no cycle is found from that node to avoid revisiting those paths again.

Solution

Cycle Detection (DFS)

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """
    Determines if it is possible to finish all courses given the prerequisites.


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


    Returns:
        True if it is possible to finish all courses, otherwise False.
    """
    # Map each course to its prerequisites
    pre_map = {i: [] for i in range(num_courses)}
    for crs, pre in prerequisites:
        pre_map[crs].append(pre)


    # Store all courses along the current DFS path
    visiting = set()


    def dfs(crs):
        if crs in visiting:
            # Cycle detected
            return False
        if not pre_map[crs]:
            return True


        visiting.add(crs)
        for pre in pre_map[crs]:
            if not dfs(pre):
                return False
        visiting.remove(crs)
        pre_map[crs] = []
        return True


    for c in range(num_courses):
        if not dfs(c):
            return False
    return True

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