Course Schedule

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.

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

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.

Approach

Use topological sorting (Kahn's algorithm). Build a graph of prerequisites and an indegree count for each course. Repeatedly take courses with indegree 0 and reduce the indegree of their neighbors. If all courses are processed, there is no cycle.

Why It Works

A valid schedule exists iff the prerequisite graph is acyclic. Kahn's algorithm removes nodes with no incoming edges; if a cycle exists, some nodes will never reach indegree 0. Therefore, processing all courses implies feasibility, and failing to do so implies a cycle.

Complexity

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

Reference Implementation (Python)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for course, pre in prerequisites:
            graph[pre].append(course)
            indeg[course] += 1

        queue = deque([i for i in range(numCourses) if indeg[i] == 0])
        taken = 0
        while queue:
            node = queue.popleft()
            taken += 1
            for nei in graph[node]:
                indeg[nei] -= 1
                if indeg[nei] == 0:
                    queue.append(nei)
        return taken == numCourses