Back to Problem
Official 322 views

Editorial: Course Schedule

by admin ·

32

1 Intuition

All courses can be finished iff the prerequisite graph has no cycle.

2 Approach

Kahn's algorithm: repeatedly take a course with no remaining prerequisites. If every course gets taken, there is no cycle.

3 Complexity Analysis

Time O(V + E), Space O(V + E).

4 Solution Code 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        indeg = [0] * numCourses
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1
        queue = [c for c in range(numCourses) if indeg[c] == 0]
        taken = 0
        while queue:
            c = queue.pop()
            taken += 1
            for nxt in graph[c]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    queue.append(nxt)
        return taken == numCourses

5 Code Walkthrough

The reference solution below implements the approach step by step.