Course Schedule medium

Problem Statement

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

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.

Steps to Solve

1. Create an adjacency list: Represent the courses and their prerequisites as a directed graph using an adjacency list. Each course will be a node, and a directed edge from course b to course a indicates that b is a prerequisite for a.

2. Detect cycles: Use Depth First Search (DFS) to detect cycles in the graph. If a cycle is detected, it means there's a circular dependency between courses, making it impossible to finish all courses. We'll use a visited array to track the nodes currently being visited and a recursion_stack to track nodes currently in the recursion stack.

3. Topological Sort (Optional): While cycle detection is sufficient, a topological sort can be performed as well. If a topological sort is possible, it means there are no cycles, and you can finish all courses.

Explanation

The core idea is to model the problem as a directed graph and check for cycles. A cycle in the graph indicates a circular dependency, making it impossible to complete all courses. DFS is an efficient way to detect cycles in a directed graph. When we encounter a node already in the recursion_stack, we've found a cycle.

Code

def canFinish(numCourses, prerequisites):
    """
    Determines if it's possible to finish all courses given prerequisites.

    Args:
        numCourses: The total number of courses.
        prerequisites: A list of lists, where each inner list represents a prerequisite [course, prerequisite].

    Returns:
        True if all courses can be finished, False otherwise.
    """

    # Create adjacency list
    graph = [[] for _ in range(numCourses)]
    for course, pre in prerequisites:
        graph[pre].append(course)

    visited = [0] * numCourses  # 0: unvisited, 1: visiting, 2: visited
    recursion_stack = [False] * numCourses

    def dfs(node):
        visited[node] = 1  # Mark as visiting
        recursion_stack[node] = True

        for neighbor in graph[node]:
            if visited[neighbor] == 0:
                if not dfs(neighbor):
                    return False
            elif recursion_stack[neighbor]:
                return False  # Cycle detected

        recursion_stack[node] = False
        visited[node] = 2  # Mark as visited
        return True

    for node in range(numCourses):
        if visited[node] == 0:
            if not dfs(node):
                return False

    return True

Complexity

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is due to the DFS traversal of the graph.

• Space Complexity: O(V), primarily due to the visited and recursion_stack arrays, which store information about each course. The adjacency list also takes O(V+E) space but is dominated by the arrays in most cases.