LeetCode 207: Course Schedule — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Graph | Topological Sort | BFS | Cycle Detection

The Problem

Determine if it's possible to finish all courses given a list of prerequisite pairs, where each pair [a,b] indicates course a requires course b to be completed first.

Approach

Use topological sorting with Kahn's algorithm to detect cycles in the course dependency graph. Build a graph and track in-degrees, then process courses with no prerequisites first, removing edges and checking if all courses can eventually be processed.

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

Code

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        in_degree = [0] * numCourses

        # Construct the graph and count in-degrees
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Initialize a queue with nodes having in-degree zero
        queue = collections.deque(
            [course for course, degree in enumerate(in_degree) if degree == 0]
        )

        # Perform topological sorting and update in-degrees
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        # If any course has in-degree greater than zero, there's a cycle
        return all(degree == 0 for degree in in_degree)