Course Schedule

There are numCourses courses labeled 0 to numCourses minus 1. You are given a list of prerequisite pairs where [a, b] means you must finish course b before course a. Determine whether it is possible to finish every course. It is possible exactly when the prerequisite graph has no cycle.

Example#

With numCourses = 2 and prerequisites = [[1, 0]], you take 0 then 1, so the answer is true. With prerequisites = [[1, 0], [0, 1]], course 1 needs 0 and course 0 needs 1, a cycle, so the answer is false.

Brute force note#

You could try every ordering of courses and check validity, but that is factorial time and hopeless for more than a handful of courses. Cycle detection is the real question, and topological sorting answers it directly.

Optimal approach#

Model courses as nodes and prerequisites as directed edges from b to a. Compute each node’s in-degree (number of prerequisites). Repeatedly take any node with in-degree zero, “complete” it, and decrement the in-degree of its dependents. If you can complete all numCourses nodes this way, there is no cycle. If you get stuck with nodes remaining, a cycle exists. This is Kahn’s algorithm.

 1from collections import deque
 2
 3
 4def can_finish(num_courses, prerequisites):
 5    graph = [[] for _ in range(num_courses)]
 6    indegree = [0] * num_courses
 7    for course, pre in prerequisites:
 8        graph[pre].append(course)
 9        indegree[course] += 1
10
11    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
12    completed = 0
13    while queue:
14        node = queue.popleft()
15        completed += 1
16        for nxt in graph[node]:
17            indegree[nxt] -= 1
18            if indegree[nxt] == 0:
19                queue.append(nxt)
20    return completed == num_courses
21
22
23print(can_finish(2, [[1, 0]]))          # True
24print(can_finish(2, [[1, 0], [0, 1]]))  # False

Complexity#

Time is O(V + E) where V is numCourses and E is the number of prerequisites: you build the graph and process each edge once. Space is O(V + E) for the adjacency list, in-degree array, and queue.

This is the canonical use of the topological sort pattern. Cement it, then move on through the 60-day curriculum.