Course Schedule — Kahn's Algorithm (BFS Topological Sort) for Cycle Detection

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] = [a, b] indicates that you must take course b first if you want to take course a. Return true if you can finish all courses; otherwise return false.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• All pairs are distinct.

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take 0 then 1.

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Cycle: 0 needs 1, 1 needs 0.

Input:  numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
Output: true
Explanation: Take 0 -> 1 -> 2 -> 3.

Why This Problem Matters#

LeetCode 207 Course Schedule is a staple at Amazon, Google, Meta, and Microsoft. It is the prototypical cycle detection in a directed graph problem and a clean application of Kahn's algorithm (BFS topological sort using a queue and indegree array).

Real-world applications of topological sort:

• Build systems: ordering compilation tasks (Bazel, Make, Gradle).
• Task scheduling: which jobs can run in parallel; which must wait.
• Spreadsheet recalculation: which cells must be recomputed and in what order.
• Package managers: installing dependencies before dependents (npm, pip, apt).
• Course planning (literally what this problem models).

If you can confidently solve LC 207, you unlock LC 210 (Course Schedule II), LC 269 (Alien Dictionary), LC 310 (Minimum Height Trees), LC 444 (Sequence Reconstruction), and more.

The Core Insight#

Model the courses as a directed graph: an edge b -> a means "course b is a prerequisite of course a." You can finish all courses if and only if this graph has no cycle (it is a DAG, directed acyclic graph).

Kahn's algorithm does cycle detection and topological ordering in one pass:

1. Compute the indegree of every node (how many prerequisites it has).
2. Push all nodes with indegree 0 into a queue (they have no prerequisites).
3. Pop a node, "remove" its outgoing edges by decrementing the indegree of each child. Whenever a child's indegree reaches 0, push it.
4. Count how many nodes you popped. If the count equals numCourses, the graph is a DAG. Otherwise some nodes were stuck in a cycle.

The DFS alternative uses three colors: white (unvisited), gray (in current path), black (fully processed). Hitting a gray node means a back edge, which means a cycle.

Both run in O(V + E). Kahn's BFS is preferred in interviews because it produces a topological order as a natural side product (useful for the LC 210 follow-up).

Visual Dry Run#

Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]].

Graph: 0 -> 1 -> 2 -> 3. Indegrees: [0, 1, 1, 1].

Processed = 4 = numCourses, so the answer is true.

Cycle example: numCourses = 2, prerequisites = [[1,0],[0,1]].

Indegrees: [1, 1]. Queue starts empty. We pop nothing. Processed = 0 != 2, so the answer is false.

Solution (Optimal)#

# Python — Kahn's algorithm (BFS topological sort), O(V+E) time, O(V+E) space
from collections import deque, defaultdict
 
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    indegree = [0] * numCourses
 
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1
 
    queue = deque(i for i in range(numCourses) if indegree[i] == 0)
    processed = 0
 
    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
 
    return processed == numCourses

// JavaScript — Kahn's algorithm, O(V+E) time, O(V+E) space
function canFinish(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);
 
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
        indegree[course]++;
    }
 
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
 
    let processed = 0;
    while (queue.length) {
        const node = queue.shift();
        processed++;
        for (const next of graph[node]) {
            if (--indegree[next] === 0) queue.push(next);
        }
    }
 
    return processed === numCourses;
}

# Python — DFS with three-color cycle detection, O(V+E) time, O(V+E) space
def canFinishDFS(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
 
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * numCourses
 
    def dfs(node: int) -> bool:
        if color[node] == GRAY:
            return False  # back edge -> cycle
        if color[node] == BLACK:
            return True
        color[node] = GRAY
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        color[node] = BLACK
        return True
 
    return all(dfs(i) for i in range(numCourses))

Complexity:

Common Mistakes#

1. Reversing the edge direction. [a, b] means "to take a, you need b first," so the edge is b -> a, not a -> b. Building the graph the wrong way still detects a cycle but yields the wrong topological order in the LC 210 follow-up.

2. Forgetting isolated nodes. Courses with no prerequisites still must be enqueued at the start. If you build the queue from prerequisites instead of iterating range(numCourses), you miss them.

3. Using a set instead of a deque as the queue. A set has no defined dequeue order; correctness still holds for cycle detection but the topological order becomes nondeterministic, which can fail strict checkers.

4. DFS without three colors. A simple visited set cannot distinguish "currently on the path" from "already finished," so it falsely flags every shared ancestor as a cycle.

5. Not handling self-loops. prerequisites = [[0,0]] is a cycle by itself. Kahn's algorithm handles it naturally because indegree of 0 is 1 and never decrements; DFS sees it on the first recursive call.

Interview Tips#

• Open with: "I will model this as a directed graph and check whether it is a DAG. Kahn's algorithm using BFS gives O(V+E) and naturally yields a valid order if one exists."
• Walk through the indegree intuition before coding: "An indegree-zero node has all its prerequisites satisfied; we can take it now."
• After coding, verify by running through a tiny cycle and a tiny chain on the whiteboard. Verbalize the processed == numCourses check.
• If asked about DFS, mention the three-color trick. Many candidates use a single visited set and silently break.
• Mention real applications (build systems, package managers) — interviewers love practical context.

Follow-up Questions#

1. Course Schedule II (LC 210). Return one valid order. Kahn's BFS already collects this — just append node to a result list inside the loop.
2. Alien Dictionary (LC 269). Derive a topological order from a list of words.
3. Parallel Course Schedule (LC 1136 / 2050). Minimum semesters when courses can be taken in parallel — Kahn's BFS but track levels.
4. Detect cycle in undirected graph. Use Union-Find or DFS with parent tracking — different from directed cycle detection.
5. Critical path / longest path in a DAG. Topological order then DP for longest path.

Key Takeaways#

• Course Schedule reduces to "is the prerequisite graph a DAG?" — solvable with Kahn's BFS topological sort.
• Kahn's algorithm uses a queue (FIFO) plus an indegree array; pop indegree-zero nodes and decrement their children.
• If the count of processed nodes equals numCourses, the graph is acyclic; otherwise a cycle exists.
• DFS with three-color (white, gray, black) is the alternate cycle-detection approach; gray-on-gray means a back edge.
• Both approaches run in O(V + E) time and space — optimal because every edge must be inspected.
• The pattern generalizes to LC 210, LC 269 Alien Dictionary, parallel course scheduling, and any dependency-resolution system.