Frontend Beauty
ESC

Type to search the knowledge base.

Course Schedule II

Return a valid course order (topological sort) or empty array if a cycle exists — Kahn BFS and DFS postorder.

intermediate3 min read
  • dsa
  • graph
  • interview
  • Google
  • Meta

The problem

Same setup as Course Schedule: [a, b] means take b before a. Return any valid order of all courses, or [] if impossible.

numCourses = 4, prereq = [[1,0],[2,0],[3,1],[3,2]]
One answer: [0,1,2,3] or [0,2,1,3]

Kahn’s BFS (natural for “order”)

  1. Build graph + indegrees.
  2. Queue all indegree-0 nodes.
  3. Pop, append to order, decrement neighbors; enqueue when indegree hits 0.
  4. If order length < n → cycle → [].
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array<number>(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    g[b].push(a);
    indeg[a]++;
  }

  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);

  const order: number[] = [];
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    order.push(u);
    for (const v of g[u]) {
      if (--indeg[v] === 0) q.push(v);
    }
  }

  return order.length === numCourses ? order : [];
}
Time O(V + E)
Space O(V + E)

DFS postorder

Push node to result after processing neighbors (reverse postorder of the dependency DAG). Detect gray back-edges for cycles.

function findOrderDfs(numCourses: number, prerequisites: number[][]): number[] {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) g[b].push(a);

  const state = new Array<number>(numCourses).fill(0);
  const order: number[] = [];
  let cycle = false;

  function dfs(u: number) {
    if (cycle) return;
    if (state[u] === 1) {
      cycle = true;
      return;
    }
    if (state[u] === 2) return;
    state[u] = 1;
    for (const v of g[u]) dfs(v);
    state[u] = 2;
    order.push(u); // postorder
  }

  for (let i = 0; i < numCourses; i++) if (state[i] === 0) dfs(i);
  if (cycle) return [];
  return order.reverse();
}

Because edges mean “prereq → course”, reverse postorder is a valid topo order.

Edge cases

  • No edges → any permutation, typically 0..n-1
  • Cycle → []
  • Multiple valid orders — any accepted
  • Single course

Common mistakes

  • Returning partial order when cycle exists
  • Wrong edge direction
  • DFS pushing before children (preorder) without reverse

Interview delivery

  1. Topo sort problem.
  2. Kahn with indegrees is easiest to narrate.
  3. Empty array on cycle.
  4. O(V+E).
  5. Link to Course Schedule I (boolean only).

Mental model

Same graph as Course Schedule I, but emit an order. Kahn’s algorithm literally builds the order as it peels zero-indegree nodes. Multiple valid orders exist; tests accept any.

If the interviewer asks for lexicographically smallest order, use a min-heap instead of a FIFO queue for zero-indegree nodes.

Failure mode

Returning a partial order when a cycle exists is a common bug — always check order.length === numCourses before returning.

Out-loud answer

“Topological sort of course graph. Build adjacency and indegrees, BFS from indegree zero, append to order. Empty array if we can’t place all courses. O(V+E).”

Further reading