Graphs crash course ↗ · 99

210. Course Schedule II

Given numCourses and a list of prerequisites, return a valid course order — or [] if a cycle makes it impossible. Kahn's BFS drains the graph by repeatedly processing nodes with zero incoming edges, which naturally produces a topological order and detects cycles in one pass.

● MediumTopological SortBFSKahn's AlgorithmTypeScript

PROBLEM What we're solving

You have numCourses courses labeled 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must take course b before course a. Return any valid ordering to take all courses, or [] if no valid ordering exists (i.e., there is a cycle).

Worked example: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Course 0 has no prerequisites, so start there. That unlocks 1 and 2. After both of those, 3 is unlocked. Answer: [0, 1, 2, 3] (or [0, 2, 1, 3]).

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

KEY IDEA Topological sort = process zero-indegree nodes first

Insight →A node with zero incoming edges has all its prerequisites satisfied — it can be taken right now. Remove it from the graph, which may unlock new zero-indegree nodes. Repeat. If all nodes are processed, you have a valid order. If any nodes remain (they're stuck in a cycle), return []. The count order.length === numCourses is the cycle detector.

RECIPE Kahn's BFS step by step

  • 1 · Build the graph. Create an adjacency list adj and an indegree[] array, both of size numCourses. For each [course, prereq], add an edge prereq → course and increment indegree[course]. This tracks how many unsatisfied prerequisites each course has.
  • 2 · Seed the queue. Enqueue every node whose indegree is 0 — these courses have no prerequisites and can be taken immediately.
  • 3 · BFS loop. Dequeue a node, append it to order, then decrement the indegree of each neighbor. If a neighbor's indegree hits zero, enqueue it. This simulates "completing" the course and unlocking dependent courses.
  • 4 · Cycle check. After the loop, if order.length === numCourses every course was reachable — no cycle. Otherwise, some courses are stuck in a cycle and were never dequeued. Return [].
Classic confusion →It's easy to reverse the edge direction. The prerequisite pair [a, b]means "take b before a", so the directed edge goes b → a (prereq points to dependent). Many learners accidentally build the reversed graph a → b and get nonsense orderings without an obvious error.

COST Complexity & alternatives

DFS with visited coloring
O(V + E)
Same asymptotic cost; builds the stack in reverse; harder to get right.
Kahn's BFS
O(V + E)
Each node enqueued once; each edge visited once. Cycle detection is free.

Space is O(V + E) for the adjacency list and indegree array. The queue holds at most Vnodes. Both DFS and BFS are optimal; prefer Kahn's when you also need to detect a cycle (the order.length check) without separate bookkeeping.

Pattern transfer → Kahn's BFS applies whenever you need a dependency ordering: Course Schedule I (just check order.length === n), Alien Dictionary (build graph from character ordering), Minimum Height Trees (repeatedly peel leaf nodes), and Parallel Courses (BFS level = semester number).

RUN IT Kahn's BFS: drain indegrees, build order

step 0 / 9
STARTBuilt adjacency list and indegree array. Seed queue with all zero-indegree nodes: [0].
1function findOrder(numCourses: number, prerequisites: number[][]): number[] {
2▶  const adj: number[][] = Array.from({ length: numCourses }, () => []);
3▶  const indegree: number[] = new Array(numCourses).fill(0);
4 
5▶  for (const [course, prereq] of prerequisites) {
6▶    adj[prereq].push(course);   // prereq → course
7▶    indegree[course]++;
8  }
9 
10▶  const queue: number[] = [];
11▶  for (let i = 0; i < numCourses; i++) {
12▶    if (indegree[i] === 0) queue.push(i);  // seed: no prerequisites
13  }
14 
15  const order: number[] = [];
16  while (queue.length > 0) {
17    const node = queue.shift()!;
18    order.push(node);
19    for (const neighbor of adj[node]) {
20      indegree[neighbor]--;
21      if (indegree[neighbor] === 0) queue.push(neighbor);
22    }
23  }
24 
25  return order.length === numCourses ? order : [];
26}
node (indegree)00112132
State
{ 0:[1,2], 1:[3], 2:[3], 3:[] }
adj
[0, 1, 1, 2]
indegree
[0]
queue
—
node
[]
order
0
processed
currently processingin queue (ready)added to orderadjacency listcurrent node
slowfast

TYPESCRIPT The solution, annotated

findOrder.ts
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree: number[] = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course);   // prereq → course
    indegree[course]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);  // seed: no prerequisites
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of adj[node]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return order.length === numCourses ? order : [];
}

Reading it block by block

Lines 2–7 — build the graph. adj[prereq].push(course) records the directed edge from prerequisite to dependent course. indegree[course]++ counts how many unsatisfied prerequisites each course has. Both structures drive the BFS.
Lines 9–11 — seed the queue. Any course with indegree[i] === 0has no prerequisites — it can be taken immediately. This is the "starting set" for the BFS.
Lines 13–20 — BFS loop. Dequeue a course, append it to order(it's "completed"), then decrement every dependent course's indegree. When a dependent's indegree reaches zero, all its prerequisites are done — enqueue it. Each node is processed exactly once and each edge is visited exactly once, giving O(V + E).
Line 22 — cycle detection. After the loop, if order.length === numCourses every course was dequeued — the graph is acyclic and orderis a valid topological order. Otherwise, some courses were never dequeued because their indegrees never reached zero (they're in a cycle). Return [].
Complexity → O(V + E) time — each of the V nodes is enqueued and dequeued once; each of the E edges is traversed once to decrement indegrees. O(V + E) space for the adjacency list; O(V) for the queue and order arrays.

INTERVIEWFollow-ups they'll ask

  • "Can you detect a cycle without Kahn's?" Yes — DFS with three colors: white (unvisited), gray (in current path), black (fully processed). A gray → gray back-edge signals a cycle.
  • "What if you only need to know if a valid order exists, not return it?" That's Course Schedule I (LC 207). Same algorithm — just return order.length === numCourses instead of order.
  • "What if courses have weights (time to complete)?" Track the earliest start time per node using earliest[neighbor] = Math.max(earliest[neighbor], earliest[node] + weight) during BFS — this is the "critical path" in project scheduling.
  • "How many semesters are needed?" BFS level-by-level (process the entire queue before moving to the next batch). Each level = one semester. This is Parallel Courses (LC 1136).
  • "What if there are multiple valid orders — how do you get the lexicographically smallest?" Replace the FIFO queue with a min-heap — always process the smallest available node.

OPTIMAL Topological Sort

findOrder.ts
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree: number[] = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course);   // prereq → course
    indegree[course]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);  // seed: no prerequisites
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of adj[node]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return order.length === numCourses ? order : [];
}
Complexity → O(V + E) time — each of the V nodes is enqueued and dequeued once; each of the E edges is traversed once to decrement indegrees. O(V + E) space for the adjacency list; O(V) for the queue and order arrays.

ALT 1 Brute force — repeatedly scan for a zero-prereq course

O(V² + V·E) time · O(V + E) space

Topological sort the slow way: each round, scan all courses for one whose prerequisites are all already taken, append it to the order, and mark it done — repeat until nothing changes. If a full scan adds nobody but courses remain, there's a cycle.

approach-2.ts
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const prereqs: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) prereqs[course].push(prereq);

  const taken: boolean[] = new Array(numCourses).fill(false);
  const order: number[] = [];

  for (let round = 0; round < numCourses; round++) {
    let progressed = false;
    for (let c = 0; c < numCourses; c++) {        // full scan every round
      if (taken[c]) continue;
      if (prereqs[c].every((p) => taken[p])) {     // all prereqs satisfied
        taken[c] = true;
        order.push(c);
        progressed = true;
      }
    }
    if (!progressed) break;   // stuck → remaining courses form a cycle
  }

  return order.length === numCourses ? order : [];
}
Note → Each round rescans every course and rechecks its prerequisites, so a chain of length V costs up to O(V² + V·E). Kahn's algorithm (the optimal) tracks indegrees and only re-examines a course's neighbors when its indegree drops, sorting in O(V + E).

MNEMONIC The one-liner

"Zero indegree = ready to go. Drain it, drop neighbors' counts. If all drained — no cycle."

TRIGGERS When you see ___ → reach for ___

"must take X before Y" / dependency orderingKahn's BFS topological sort
detect a cycle in a directed graphcheck order.length vs numCourses
"how many rounds / semesters" (parallel processing)BFS level-by-level
"alien dictionary / reconstruct order from constraints"build graph → 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 [course, prereq] of prerequisites) {
  adj[prereq].push(course);
  indegree[course]++;
}
const queue: number[] = [];
for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
const order: number[] = [];
while (queue.length > 0) {
  const node = queue.shift()!;
  order.push(node);
  for (const nb of adj[node]) {
    if (--indegree[nb] === 0) queue.push(nb);
  }
}
return order.length === n ? order : [];

FLASHCARDS Tap to flip

What does indegree[i] represent?
The number of unprocessed prerequisites course i still has before it can be taken.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
For numCourses = 4 and prerequisites = [[1,0],[2,0],[3,1],[3,2]], which of the following is a valid output?
QUESTION 02
What does Kahn's algorithm return when a cycle is detected?
QUESTION 03
What is the time complexity of the topological sort using Kahn's BFS?
QUESTION 04
For prerequisites = [[a, b]], which directed edge is added to the adjacency list?
QUESTION 05
What happens to a node in a cycle during Kahn's BFS?
QUESTION 06
Which data structure naturally models the "courses ready to take right now" set?
QUESTION 07
After running Kahn's on numCourses = 2, prerequisites = [[0,1],[1,0]], how many nodes end up in order?
QUESTION 08
#210 · Course Schedule IIKahn's BFS topological sort: enqueue all indegree-0 nodes, append each dequeued node to the result, and decrement neighbors' indegrees. A cycle leaves nodes undequeued — return [] in that case.Which algorithmic approach does this primarily use?
QUESTION 09
#210 · Course Schedule IIKahn's BFS topological sort: enqueue all indegree-0 nodes, append each dequeued node to the result, and decrement neighbors' indegrees. A cycle leaves nodes undequeued — return [] in that case.Which implementation correctly solves it?