Course Schedule — Cycle Detection via Topological Sort

Problem Statement#

LeetCode 207 — Course Schedule (Medium)

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, 0 <= a, b smaller than numCourses, a != b
• All pairs (a, b) are distinct.

Example 1:

numCourses = 2, prerequisites = [[1,0]]
Output: true (take 0, then 1)

Example 2:

numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false (circular dependency)

Why This Problem Matters#

Course Schedule is one of the most asked graph questions at FAANG, especially Amazon, Google, and Meta. It is the gateway problem to topological sort, which itself is the algorithmic backbone of every modern build system, package manager, task scheduler, and migration framework. If you have ever run npm install, mvn package, or bazel build, the engine inside is doing exactly what this problem asks.

Interviewers love it because:

1. Two distinct optimal solutions exist — Kahn algorithm (BFS with in-degrees) and three-color DFS. Knowing both demonstrates fluency.
2. It tests directed-graph fundamentals — adjacency list, in-degree computation, queue management.
3. The follow-up — LC 210 — Course Schedule II — asks for the actual ordering, which Kahn delivers for free.

The problem also exposes a common candidate pitfall: confusing the edge direction. prerequisites[i] = [a, b] means b must come before a, so the edge in the dependency graph goes b -> a. Reversing this is the single most common bug in the room.

The Core Insight#

The question reduces to a single graph-theoretic property: does the prerequisite graph contain a cycle? A cycle means impossible — you would need to take a course before itself. No cycle means possible.

Two standard cycle-detection algorithms in directed graphs:

• Kahn algorithm (BFS): Start with all zero-in-degree nodes. Repeatedly pop one, decrement the in-degree of its successors, push any successor whose in-degree hits zero. Count how many nodes were processed; if fewer than numCourses, a cycle exists.
• Three-color DFS: White = unvisited, Gray = in current DFS path, Black = fully explored. If DFS encounters a Gray node, you have found a back edge, hence a cycle.

Both are O(V + E). Kahn is preferable when you also need the ordering. DFS is preferable when you want elegant recursion or are comfortable with the recursion-stack risk.

Visual Dry Run#

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Build the graph (edge b -> a):

Edges (direction = prerequisite -> course):
  0 -> 1
  0 -> 2
  1 -> 3
  2 -> 3
 
In-degrees: [0:0, 1:1, 2:1, 3:2]
 
Kahn step 1: queue starts with all zero in-degree -> [0]
  Pop 0. Successors 1, 2: decrement in-degrees -> [1:0, 2:0]
  Both hit zero -> push 1, 2.
  Processed = 1.
 
Kahn step 2: queue = [1, 2]
  Pop 1. Successor 3: in-degree 2 -> 1.
  Pop 2. Successor 3: in-degree 1 -> 0. Push 3.
  Processed = 3.
 
Kahn step 3: queue = [3]
  Pop 3. No successors.
  Processed = 4.
 
Processed count == numCourses -> return true.

If we had added edge 3 -> 0, none of the in-degrees would have started at zero — Kahn cannot begin, processed stays at 0, and we return false.

Solution (Optimal)#

Python (Kahn — BFS Topological Sort)#

from collections import deque, defaultdict
 
class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        adj = defaultdict(list)                 # adjacency list: prerequisite -> [courses]
        in_degree = [0] * numCourses            # how many prereqs each course needs
 
        # Edge direction: b -> a, because b must come before a
        for a, b in prerequisites:
            adj[b].append(a)
            in_degree[a] += 1
 
        # Seed the queue with everything that has no prerequisites
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        processed = 0
 
        while queue:
            course = queue.popleft()
            processed += 1                      # one more course finished
            for nxt in adj[course]:
                in_degree[nxt] -= 1             # this prerequisite is now satisfied
                if in_degree[nxt] == 0:
                    queue.append(nxt)           # ready to be taken
 
        # If we processed fewer than numCourses, a cycle blocked progress
        return processed == numCourses

JavaScript (Three-Color DFS)#

/**
 * White (0) = unvisited, Gray (1) = in current path, Black (2) = fully explored.
 * Encountering a Gray node means a back edge -> cycle.
 */
var canFinish = function(numCourses, prerequisites) {
    const adj = Array.from({length: numCourses}, () => []);
    for (const [a, b] of prerequisites) adj[b].push(a);  // b -> a
 
    const color = new Array(numCourses).fill(0);          // 0 = white
 
    const hasCycle = (u) => {
        if (color[u] === 1) return true;                  // gray -> back edge
        if (color[u] === 2) return false;                 // already proven safe
        color[u] = 1;                                     // mark gray (in path)
        for (const v of adj[u]) {
            if (hasCycle(v)) return true;                 // propagate cycle up
        }
        color[u] = 2;                                     // mark black (done)
        return false;
    };
 
    for (let i = 0; i < numCourses; i++) {
        if (color[i] === 0 && hasCycle(i)) return false;  // disconnected components
    }
    return true;
};

Complexity. Both solutions run in O(V + E) time and O(V + E) space, where V is numCourses and E is the number of prerequisite pairs.

Common Mistakes#

1. Reversing the edge direction. [a, b] means b must come before a, so edge goes b -> a. Many candidates write a -> b and produce a wrong answer that passes some tests by luck.
2. Marking visited like an undirected graph. A simple boolean visited array does not detect cycles. You need either in-degree tracking (Kahn) or three colors (DFS). A two-color DFS (visited / not visited) cannot distinguish a cross-edge from a back-edge.
3. Recursion depth on chain prerequisites. With 2,000 courses chained linearly, Python recursion blows the default limit. Use Kahn or bump sys.setrecursionlimit.
4. Not handling disconnected components. Always loop over every node when seeding the algorithm. A cycle can hide inside a component disconnected from any zero-in-degree node.
5. Building the adjacency list inside a per-query function. Doing this for many queries is wasteful — preprocess once if the graph is reused.

Interview Tips#

• Verbalize the graph construction. "I will treat each course as a node and each prerequisite [a, b] as a directed edge from b to a." This sentence prevents the direction bug before it happens.
• Pick Kahn if asked for the order, DFS if asked for elegance. Most interviewers prefer Kahn because it generalizes to LC 210 directly.
• Mention dependency-resolution analogies. Saying "this is exactly what npm and Maven do" anchors the answer in the real world and impresses senior interviewers.
• Show how you detect cycles. Saying "I count processed nodes; if fewer than total, a cycle exists" demonstrates that you understand why Kahn works.

Follow-up Questions#

1. Return the actual course order. That is LC 210. Same Kahn template — record the dequeue order.
2. Find any one cycle. Run three-color DFS and capture the path between gray nodes.
3. Minimum number of semesters with parallel classes. That is LC 1494. Use BFS by levels and the highest level depth gives the answer.
4. Edges arriving online. Use incremental cycle detection. Insert each edge and run a localized DFS from the new edge target to its source.
5. Weighted prerequisites with deadlines. Convert to a constrained scheduling problem; topological sort plus DP solves longest path.

Key Takeaways#

• Course Schedule is the gateway topological-sort problem; recognizing the cycle-detection structure is the unlock.
• Edge direction is prerequisite -> course; reversing it is the most common bug.
• Kahn algorithm (BFS with in-degrees) is the preferred choice because it generalizes to ordering and partial-order queries.
• Three-color DFS detects cycles via gray (in-path) nodes and works elegantly for recursive solutions.
• Both algorithms run in O(V + E) time and space, the optimal asymptotic bound.
• Topological sort underlies real-world systems like npm, Maven, Bazel, and Make — calling out the analogy demonstrates seniority.