Frontend Beauty
ESC

Type to search the knowledge base.

Course Schedule

Can you finish all courses given prerequisites — cycle detection in a directed graph via DFS colors or Kahn’s BFS.

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

The problem

numCourses labeled 0..n-1. Prerequisites [a, b] means take b before a (edge b → a). Return whether you can finish all courses.

numCourses = 2, prereq = [[1,0]] → true  // 0 then 1
numCourses = 2, prereq = [[1,0],[0,1]] → false // cycle

This is directed cycle detection / topological sort feasibility.

Model

Build adjacency list: b → a for each [a,b]. Cycle ⇒ impossible.

Approach A — DFS 3-color

  • 0 white (unvisited), 1 gray (in stack), 2 black (done)
  • Edge to gray ⇒ back edge ⇒ cycle
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  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); // 0/1/2

  function hasCycle(u: number): boolean {
    if (state[u] === 1) return true;
    if (state[u] === 2) return false;
    state[u] = 1;
    for (const v of g[u]) {
      if (hasCycle(v)) return true;
    }
    state[u] = 2;
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (state[i] === 0 && hasCycle(i)) return false;
  }
  return true;
}
Time O(V + E)
Space O(V + E)

Approach B — Kahn’s algorithm (BFS indegrees)

function canFinishKahn(numCourses: number, prerequisites: number[][]): boolean {
  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);

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

If you process fewer than numCourses nodes, a cycle remains.

Edge cases

  • No prerequisites → true
  • Self-loop [0,0] → false
  • Disconnected components
  • Multiple edges (rare)

Common mistakes

  • Wrong edge direction (take carefully: [a,b] means b before a)
  • Only 2-state visited without “in recursion stack”
  • Forgetting isolated courses

Interview delivery

  1. Graph + cycle detection.
  2. Clarify edge direction.
  3. Implement DFS colors or Kahn.
  4. O(V+E).
  5. Mention Course Schedule II returns the order.

Mental model

Prerequisites form a directed graph. Finishing all courses means a topological order exists, which for finite digraphs is equivalent to acyclicity.

Pick an edge convention and stick to it. LC: [a,b] means edge b→a (b before a). Drawing two nodes with a cycle is the best null-case test.

When to use Kahn vs DFS

  • Kahn: natural if you later need the order (Schedule II).
  • DFS colors: natural if you only need boolean and already think in recursion.
    Both O(V+E).

Out-loud answer

“Model prereqs as digraph; detect cycle. I’ll use indegrees and BFS: queue zero-indegree nodes, reduce neighbors, count processed. If count < numCourses there’s a cycle. Alternatively DFS with gray/black states.”

Further reading