HARD Lab · Graphs · 44

207. Course Schedule

Given numCourses and a list of prerequisite pairs, decide whether you can finish all courses — which is true exactly when the dependency graph contains no cycle. Kahn's BFS topological sort detects cycles in one pass by counting how many nodes it can fully process.

● MediumTopological SortCycle DetectionTypeScript

PROBLEM What we're solving

You have numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] means “you must take b before a.” Can you complete all courses?

Example: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Taking 0, then 1 and 2 (order either way), then 3 works → true.

Cycle example: numCourses = 2, prerequisites = [[1,0],[0,1]]. You need 0 before 1 and 1 before 0 — impossible → false.

KEY IDEA A valid schedule exists iff the graph is a DAG

Insight → prerequisites form a directed graph. Completing all courses is possible if and only if that graph has no cycle — i.e. it is a Directed Acyclic Graph (DAG). Kahn's algorithm detects cycles by counting: if BFS topological sort processes every node, no cycle exists; if some nodes are left over, they are stuck in a cycle.

RECIPE Kahn's BFS — shrink indegrees, drain the queue

  • 1 · Build the graph. For each pair [a, b], add edge b → a (b unlocks a) and increment indegree[a].
  • 2 · Seed the queue. All courses with indegree === 0 have no prerequisites — they can be taken right now.
  • 3 · BFS loop. Dequeue a course, increment finished, and for each neighbor decrement its indegree. If that neighbor's indegree hits 0, enqueue it.
  • 4 · Verdict. finished === numCourses → no cycle, true; otherwise a cycle trapped some courses.
Classic confusion → the edge direction matters. A prerequisite pair [a, b]means “b before a” — the directed edge goes from b to a, not a → b. Reversing this gives wrong indegrees and a broken sort.

COST Complexity & alternatives

DFS cycle-coloring (3-color)
O(V+E)
Also correct, but needs explicit “grey/black/white” state per node.
Kahn's BFS
O(V+E)
Same asymptotic cost; also produces the topological order for free.

Both approaches are O(V + E) time and O(V + E)space. Kahn's is usually easier to implement iteratively (no recursion depth concern) and also gives you the actual topological order — useful in Course Schedule II.

Pattern transfer → the same BFS-indegree pattern solves Course Schedule II (return the order, not just true/false), Alien Dictionary (build the graph from letter ordering constraints), Minimum Height Trees (peel leaves iteratively), and Task Scheduler dependency variants.

RUN IT Kahn's BFS — shrink indegrees until the queue empties

step 0 / 9
STARTBuild graph and compute indegrees. Each course with indegree 0 has no prerequisites — enqueue them first.
State
[0, 1, 1, 2]
indegrees
(empty)
queue
0
finished
current queueprocessed ordercycle (never dequeued)indegree state
slowfast

TYPESCRIPT The solution, annotated

canFinish.ts
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // Build adjacency list and indegree counter
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree: number[] = new Array(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    adj[b].push(a);   // b must be taken before a  =>  edge b -> a
    indegree[a]++;
  }

  // Seed the queue with all courses that have no prerequisites
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  let finished = 0;
  while (queue.length > 0) {
    const cur = queue.shift()!;
    finished++;
    for (const neighbor of adj[cur]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // If every course was processed there is no cycle
  return finished === numCourses;
}

Reading it block by block

Lines 3–9 — build the graph. adj[b].push(a) records that finishing b unlocks a; indegree[a]++ counts how many prerequisites a still has. Edge direction is b → a because b must come first.
Lines 12–14 — seed the queue. Courses with indegree === 0have no outstanding prerequisites. They are the “roots” of the DAG and can be taken immediately.
Lines 16–22 — BFS drain. Dequeue a course, count it as finished, then walk its adjacency list. Decrementing indegree[neighbor]simulates “this prerequisite is now satisfied.” When indegree reaches 0, the course is newly unlocked and joins the queue.
Line 25 — the cycle test. A cycle means a group of courses where every member still has at least one unsatisfied prerequisite pointing back into the group. They never reach indegree 0 and are never dequeued, so finished < numCourses.
Complexity → O(V + E) time: every node is enqueued and dequeued at most once; every edge is visited exactly once when we walk adj[cur]. Space is also O(V + E) for the adjacency list and O(V) for indegrees and the queue.

INTERVIEWFollow-ups they'll ask

  • “Return the actual order (Course Schedule II)?” Collect each dequeued course into a result array; return it if result.length === numCourses, else [].
  • “DFS instead of BFS?”Use 3-color DFS (white/grey/black): grey means “currently on the call stack” — if you visit a grey node, a cycle exists. Kahn's avoids recursion depth risk on very deep graphs.
  • “What if there are multiple valid orderings?” Any valid topological order is acceptable for Course Schedule. If the problem asks for lexicographic order, swap the queue for a min-heap.
  • “What about disconnected components?” Seeding the queue with allzero-indegree nodes (not just one) naturally handles disconnected graphs — each component's roots all start in the queue.
  • “Edge cases?” numCourses = 1 with no prerequisites is trivially true. An empty prerequisites list means all courses are independent and trivially orderable.

MNEMONIC The one-liner

"Count the locks on every door. Open the unlocked ones first — each door you open removes a lock from its neighbors."

TRIGGERS When you see ___ → reach for ___

"can all tasks/courses be completed" with dependenciesKahn's BFS topological sort + cycle check
directed dependency graph, detect cycleBFS indegree drain OR 3-color DFS
"return a valid ordering" of tasks with prerequisitesKahn's BFS — collect dequeued order
"no cycle" / "acyclic" / "DAG" in disguisefinished === numNodes check after topo-sort

SKELETON The reusable shape

skeleton.ts
const adj: number[][] = Array.from({ length: n }, () => []);
const indegree: number[] = new Array(n).fill(0);
for (const [a, b] of prerequisites) {
  adj[b].push(a);
  indegree[a]++;
}
const queue: number[] = [];
for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
let finished = 0;
while (queue.length > 0) {
  const cur = queue.shift()!;
  finished++;
  for (const nb of adj[cur])
    if (--indegree[nb] === 0) queue.push(nb);
}
return finished === n;

FLASHCARDS Tap to flip

What does Kahn's algorithm detect a cycle via?
If finished < numCourses after BFS, some nodes were never reachable with indegree 0 — they are stuck in a cycle.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the time complexity of Kahn's BFS topological sort on a graph with V nodes and E edges?
QUESTION 02
For prerequisites = [[1,0],[0,1]] with numCourses = 2, what happens during Kahn's algorithm?
QUESTION 03
Given numCourses = 4 and prerequisites [[1,0],[2,0],[3,1],[3,2]], what is the earliest course that can be dequeued?
QUESTION 04
What is the edge direction for a prerequisite pair [a, b] (b must be taken before a)?
QUESTION 05
After running Kahn's on a valid DAG with numCourses = 5, the finished counter equals 3. What does this mean?
QUESTION 06
How would you modify the solution to also return the course order (Course Schedule II)?
QUESTION 07
For a graph with no edges (numCourses = 5, prerequisites = []), what does canFinish return?