Course Schedule

There are numCourses courses, and prerequisite pairs [course, prereq] meaning you must take prereq before course. Can you finish every course? (LC 207)

This is the one genuinely new idea in the circuit — the others are structures, this is an algorithm. And it's everywhere once you see it: build systems, package managers, task schedulers, migration runners. Any "X must happen before Y" system is this graph.

The recipe

Say before you type: "This is cycle detection on a directed graph — a valid schedule exists iff the graph is a DAG. I'll run Kahn's: repeatedly take anything with no remaining prerequisites, and if I can't take everything, the leftovers are in a cycle."

1. Build the adjacency list with edges pointing the way you can go: prereq → course. Count each course's indegree (how many prerequisites it still needs).
2. Seed a queue with every course of indegree 0 — the ones you can take right now.
3. Repeatedly take a course; for each course it unlocks, decrement that indegree. Anything hitting 0 joins the queue.
4. Count what you took. Took everything → no cycle. Anything left is waiting on something inside a cycle.

The code

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course); // prereq -> course: the edge points the way you can go
    indegree[course]++;
  }

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

  let taken = 0;
  while (queue.length) {
    const course = queue.pop()!; // order doesn't matter for the yes/no answer
    taken++;
    for (const next of adj[course]) {
      if (--indegree[next] === 0) queue.push(next);
    }
  }
  return taken === numCourses; // leftovers = cycle
}

Why this shape

A schedule exists exactly when the dependency graph has no cycle — a cycle is two courses each waiting on the other, and nothing inside it can ever start. Kahn's algorithm simulates actually doing the work: take what's unblocked, and taking it unblocks other things. If the simulation drains the whole graph, a valid order exists (the order you drained it in!). If it stalls early, everything remaining has indegree ≥ 1 — each waiting on something that's also still waiting, which is precisely a cycle.

The line that is the whole answer: taken === numCourses. It's cycle detection and schedulability in one comparison.

Complexity

	Cost	Because
Time	O(V + E)	Each course enters the queue once; each edge is decremented once
Space	O(V + E)	The adjacency list dominates

Traps

• The direction trap. [course, prereq] reads in the opposite order from the edge you need. Build adj[prereq].push(course) — the arrow points from the thing you do first to the things it unlocks. Get it backwards and everything runs, tests half-pass, and the logic is inverted.
• For the yes/no question, pop from either end — a stack works. For Course Schedule II (return an actual order), use a real FIFO, and remember shift() is O(n): use an index pointer.
• Forgetting to seed all indegree-0 nodes. There can be many independent starting points.

The alternative: DFS with three colors

Some people find cycle-detection-by-DFS more natural; interviewers accept either, and knowing both lets you say why you chose one:

function canFinishDFS(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) adj[prereq].push(course);

  const UNVISITED = 0, VISITING = 1, DONE = 2;
  const state = new Array(numCourses).fill(UNVISITED);

  const hasCycle = (u: number): boolean => {
    if (state[u] === VISITING) return true;  // back edge = cycle
    if (state[u] === DONE) return false;     // already cleared
    state[u] = VISITING;                     // on the current path
    for (const v of adj[u]) if (hasCycle(v)) return true;
    state[u] = DONE;                         // off the path, proven safe
    return false;
  };

  for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;
  return true;
}

The three states are the point: VISITING means on the current path — meeting it again is a back edge, i.e. a cycle. A plain boolean visited set can't tell "on my path" from "explored earlier and fine," and produces false positives on diamonds.

The pattern this trains

"Prerequisites / ordering / dependencies" → topological sort. This exact algorithm, with indegree renamed to "number of unresolved dependencies," is the core of the package-registry design problem in the practical questions — same graph, same Kahn's, same finished === n check. Recognizing that a design escalation is LC 207 wearing a costume is the payoff of repping it.