4.20.8 — Course Schedule

LeetCode 207 · Medium · ★ Blind 75

The problem

There are numCourses courses. prerequisites[i] = [a, b] means you must take b before a. Return true if it is possible to finish every course.

numCourses = 2, prerequisites = [[1,0]]           →  true
numCourses = 2, prerequisites = [[1,0],[0,1]]     →  false   (each needs the other)

The pattern

Model it as a directed graph: an edge from b to a means "b must come before a".

Then the question is a single sentence:

You can finish everything exactly when the graph has no cycle.

A cycle means a set of courses each waiting for another, and none of them can ever start. Any graph without a cycle can be ordered so that every prerequisite comes first — that is what a directed acyclic graph is.

So this problem is cycle detection in a directed graph, and there are two standard ways to do it.

Method 1 — Kahn's algorithm (BFS)

Repeatedly take a course with no remaining prerequisites, do it, and remove it from everyone else's list.

• indegree[c] = how many prerequisites course c still has.
• Start with every course whose indegree is 0.
• Taking a course reduces its dependents' indegrees; any that reach 0 become available.

If you finish fewer courses than exist, the leftovers were stuck in a cycle. That check is the cycle detection — you get it for free, without ever looking for a cycle directly.

Python

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prereq in prerequisites:
            adj[prereq].append(course)       # prereq → course
            indegree[course] += 1

        queue = deque(c for c in range(numCourses) if indegree[c] == 0)
        done = 0

        while queue:
            c = queue.popleft()
            done += 1
            for nxt in adj[c]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return done == numCourses            # short → a cycle blocked the rest

TypeScript

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);
    indegree[course]++;
  }

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

  let head = 0, done = 0;
  while (head < queue.length) {
    const c = queue[head++];
    done++;
    for (const nxt of adj[c]) {
      if (--indegree[nxt] === 0) queue.push(nxt);
    }
  }

  return done === numCourses;
}

Get the edge direction right. [a, b] means b comes first, so the edge runs b → a and it is a's indegree that increases. Reversing this is the most common mistake here, and it produces answers that are right on symmetric test cases and wrong on the rest.

Array.from({length: n}, () => []), not new Array(n).fill([]). The second creates one shared array — the aliasing trap from 4.4.5.

A bonus worth knowing: everything in the queue at the same moment can be taken in parallel, since none depends on another. So the number of rounds is the minimum number of semesters, which is the natural follow-up question.

Method 2 — DFS with three states

Walk the graph, and if you ever reach a node that is currently on the path you are exploring, you have found a cycle.

Two states are not enough. "Visited" cannot distinguish finished and safe from still in progress above me, and reaching a finished node is perfectly fine — it just means a shared prerequisite. So use three:

• 0 — not visited
• 1 — in progress, on the current path
• 2 — finished, and known to be safe

Meeting a 1 is a cycle. Meeting a 2 is fine.

def canFinish(self, numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        adj[prereq].append(course)

    state = [0] * numCourses

    def has_cycle(c) -> bool:
        if state[c] == 1: return True        # back-edge → cycle
        if state[c] == 2: return False       # already cleared

        state[c] = 1                          # in progress
        for nxt in adj[c]:
            if has_cycle(nxt): return True
        state[c] = 2                          # finished
        return False

    return not any(has_cycle(c) for c in range(numCourses) if state[c] == 0)

Setting state[c] = 2 on the way out is what makes it linear. Without it, shared subtrees are re-explored and the algorithm becomes exponential on some graphs.

Note that this three-state rule is for directed graphs. In an undirected graph, cycle detection instead means "I reached an already-visited node that is not my parent", because every edge naturally goes both ways.

Complexity

O(V + E) time and space for both methods.

Which to write

Kahn's, usually. It is iterative so there is no stack depth limit, the cycle check falls out of a counter, and it extends directly to Course Schedule II by recording the order. The parallel-semesters bonus is also free.

DFS is worth knowing because the three-state idea appears elsewhere, and because some interviewers ask for it specifically.

Where this goes next

• Course Schedule II — return the order, not just whether one exists. Kahn's already computed it. 4.20.9.
• Alien Dictionary — derive the letter ordering from sorted words, then topologically sort it. 4.21.
• Minimum Height Trees — the same peeling idea from the outside in, on an undirected graph.
• Real systems — build tools (make, Bazel), package managers resolving dependencies, spreadsheet recalculation, and task schedulers all run a topological sort and all report a circular dependency error when the sort comes up short. That error message is literally done != numCourses.

What the interviewer will push on

"Restate the problem in graph terms." Cycle detection in a directed graph. Say this first; it is most of the answer.

"Which way do the edges point?" From prerequisite to course. Be explicit.

"How does Kahn's detect a cycle?" The processed count falls short, because nodes in a cycle never reach indegree 0.

"Why three states in the DFS version, not two?" To distinguish in progress from finished. Reaching a finished node is fine; reaching an in-progress one is a cycle.

"How would you find the minimum number of semesters?" Process Kahn's queue level by level and count the levels.

"How would you report which courses form the cycle?" In the DFS version, keep the current path on a stack and slice it from the repeated node.

One thing to volunteer: name a real build system. "This is what make does, and 'circular dependency detected' is exactly this check failing." It shows the algorithm is something you recognise rather than something you memorised.

Next: 4.20.9 Course Schedule II — the same algorithm, now returning the order it already computed.