LeetCode · #207

Course Schedule Solution

Given numCourses courses and a list of prerequisite pairs, determine whether it is possible to finish all courses — i.e., whether the prerequisite graph contains a cycle.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #207

🏗️

Pattern

Graph — topological sort + cycle detection

There are numCourses courses labeled 0 to numCourses-1. Given a list prerequisites where prerequisites[i] = [a, b] means you must take course b before course a, return true if all courses can be finished.

Example

 Input: numCourses = 2, prerequisites = [[1,0]]
Output: true // Take course 0, then course 1. No cycle. Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false // 0 requires 1, and 1 requires 0 — circular dependency → impossible 

Constraints

 • 1 ≤ numCourses ≤ 2000 • 0 ≤ prerequisites.length ≤ 5000  ← sparse graph, O(V+E) expected • prerequisites[i].length == 2 • No duplicate edges 

Section Two · Approach 1

DFS Cycle Detection — O(V+E)

Build an adjacency list from prerequisites. Run DFS from every unvisited node. Track three states per node: unvisited (0), in current DFS path (1), fully processed (2). If DFS reaches a node in state 1, a cycle exists. If any cycle is found, return false.

Why it works

A directed graph has a cycle if and only if a DFS encounters a "back edge" — an edge pointing to an ancestor in the current DFS tree. The three-color marking (white/grey/black) reliably detects back edges without re-exploring completed subgraphs.

Why we can also use Kahn's algorithm

Alternative insight: Kahn's BFS-based topological sort is often clearer for explaining in interviews. Start with all nodes whose in-degree is 0 (no prerequisites). Process them, reducing in-degrees of their neighbors. If all V nodes are eventually processed, no cycle exists. If the queue empties before processing all nodes, a cycle trapped those nodes with in-degree > 0 forever.

Java — DFS 3-color cycle detection

 import java.util.*;
class Solution {
public boolean canFinish(int n, int[][] pre) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : pre) adj.get(p[1]).add(p[0]);
int[] state = new int[n]; // 0=unvisited, 1=visiting, 2=done for (int i = 0; i < n; i++)
if (hasCycle(adj, state, i)) return false;
return true;
    }
private boolean hasCycle(List<List<Integer>> adj, int[] st, int v) {
if (st[v] == 1) return true; // back edge — cycle found if (st[v] == 2) return false; // already fully explored
st[v] = 1;
for (int nb : adj.get(v))
if (hasCycle(adj, st, nb)) return true;
        st[v] = 2;
return false;
    }
}

Python — DFS 3-color cycle detection

 class Solution:
def canFinish(self, n: int, prerequisites: list[list[int]]) -> bool:
        adj = [[] for _ in range(n)]
for a, b in prerequisites:
            adj[b].append(a)
        state = [0] * n # 0=unvisited 1=visiting 2=done def dfs(v: int) -> bool:
if state[v] == 1: return True # back edge if state[v] == 2: return False
state[v] = 1 if any(dfs(nb) for nb in adj[v]): return True
state[v] = 2 return False return not any(dfs(i) for i in range(n) if state[i] == 0)

Metric	Value
Time	O(V + E) — each node and edge visited once
Space	O(V + E) — adjacency list + O(V) state + O(V) call stack

Section Three · Approach 2

Kahn's BFS Topological Sort — O(V+E)

Count the in-degree of every node. Enqueue all nodes with in-degree 0. Process: dequeue a node, decrement neighbors' in-degrees, enqueue any that reach 0. If all V nodes are processed, return true; otherwise a cycle prevented some nodes from ever reaching in-degree 0.

💡 Mental model: Imagine a university registration system. A course can only open enrollment once all its prerequisites have been completed. Start by opening every course with no prerequisites. When a course is completed, lower the "remaining prerequisites" counter for every course that depended on it. Any course whose counter hits zero opens next. If all courses eventually open, the curriculum is acyclic. If some courses never open (their counter never reaches zero), there's a circular dependency that blocks them forever.

Algorithm — Kahn's BFS

Build adjacency list from prerequisites: b → a for each [a, b] pair.
Compute inDegree[i] for each node i.
Enqueue all nodes where inDegree[i] == 0.
BFS: dequeue node, increment processed, for each neighbor decrement inDegree, enqueue if it reaches 0.
Return processed == numCourses.

🎯 When to recognize this pattern:

Any "dependency ordering" or "can all tasks be done?" problem.
Signal words: "prerequisite," "dependency," "order," "schedule." Kahn's BFS gives topological order as a side effect (LC 210), while the DFS approach is slightly more compact for pure cycle detection.
Both are O(V+E) — choose whichever you can explain clearly.

Why processed == V proves no cycle:

Every node with in-degree 0 is eventually enqueued.
If a cycle exists, all nodes in the cycle have in-degree ≥ 1 always (they depend on each other) and are never enqueued.
So fewer than V nodes are processed — the deficit is exactly the cycle size.

Section Four · Trace

Visual Walkthrough

Trace Kahn's BFS on numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]. Graph: 0→1, 0→2, 1→3, 2→3.

Kahn's BFS — Course Schedule (4 courses, no cycle)

Section Five · Implementation

Code — Java & Python

Java — Kahn's BFS topological sort

 import java.util.*;
class Solution {
public boolean canFinish(int n, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDeg = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]); // p[1] → p[0]
inDeg[p[0]]++;
        }
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++)
if (inDeg[i] == 0) q.offer(i); // no prerequisites — start here int processed = 0;
while (!q.isEmpty()) {
int v = q.poll();
            processed++;
for (int nb : adj.get(v)) {
if (--inDeg[nb] == 0) q.offer(nb); // all prereqs met
}
        }
return processed == n; // false if cycle trapped nodes
}
}

Python — Kahn's BFS topological sort

 from collections import deque
class Solution:
def canFinish(self, n: int, prerequisites: list[list[int]]) -> bool:
        adj = [[] for _ in range(n)]
        in_deg = [0] * n
for a, b in prerequisites:
            adj[b].append(a)
            in_deg[a] += 1
q = deque(i for i in range(n) if in_deg[i] == 0)
        processed = 0 while q:
            v = q.popleft()
            processed += 1 for nb in adj[v]:
                in_deg[nb] -= 1 if in_deg[nb] == 0:
                    q.append(nb) # all prerequisites satisfied return processed == n

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force (try all orderings)	O(V!)	O(V)	Completely infeasible for V > 10
DFS 3-color cycle detection	O(V + E)	O(V + E)	Recursive — stack overflow risk for large V; harder to extend to ordering
Kahn's BFS ← optimal	O(V + E)	O(V + E)	Iterative — no stack overflow; yields topological order as side effect

Why not just check the adjacency matrix for cycles?:

An adjacency matrix is O(V²) space — for V=2000 that's 4M entries.
More critically, reading the matrix to detect cycles still requires graph traversal.
There's no shortcut to O(V+E) cycle detection other than actually traversing the graph.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No prerequisites	`n=5, prerequisites=[]`	All in-degrees 0 → all enqueued immediately → processed=5=n → true.
Direct cycle (2 nodes)	`[[1,0],[0,1]]`	Both have in-degree 1. Neither enters queue. processed=0 < 2 → false.
Indirect cycle (3+ nodes)	`[[1,0],[2,1],[0,2]]`	All in-degrees = 1. Queue stays empty. processed=0 → false.
Single node	`n=1, prerequisites=[]`	In-degree 0, enqueued, processed=1=n → true.
Self-loop	`[[0,0]]`	Node 0 depends on itself. in-degree = 1, never reaches 0 → false.
Disconnected graph	Some nodes with no edges	Isolated nodes have in-degree 0 and are enqueued and processed. Cycle only in one component still caught.

⚠ Common Mistake: Reversing the edge direction. The prerequisite [a, b] means "must take b before a" — the edge in the dependency graph is b → a. If you add a → b instead, you reverse all edges and compute in-degrees incorrectly. Node b would get in-degree incremented when it should be node a. Always double-check: the node that must be taken first (b) is the source; the node that depends on it (a) is the destination.

← Back to Graph problems

LearningTree

LC 207 · Course Schedule — Solution & Explanation | DSA Guide