Course Schedule

There are numCourses courses, labeled 0 to numCourses - 1. Each entry [a, b] in prerequisites means you must finish course b before you can start course a.

Return true if there is some order in which you can take every course, and false otherwise.

The same pair may appear more than once. A course that lists itself as its own prerequisite can never be taken.

Treat each course as a node and each prerequisite [a, b] as an edge b → a. You can finish everything exactly when this directed graph has no cycle: a cycle means every course in it is waiting on another course in it, so none of them can go first.

Whenever a problem says "X must happen before Y" and asks whether (or in what order) everything can happen, think topological sort. Kahn's algorithm makes the cycle check concrete: repeatedly take a course with no unfinished prerequisites, mark it done, and lower the prerequisite count of everything that depended on it. If you manage to take all numCourses courses, there was no cycle. If you get stuck with courses left over, the leftovers are tangled in a cycle.

from collections import deque


def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, before in prerequisites:
        graph[before].append(course)
        indegree[course] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    taken = 0
    while queue:
        course = queue.popleft()
        taken += 1
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return taken == num_courses

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [course, before] of prerequisites) {
    graph[before].push(course);
    indegree[course]++;
  }

  const queue = [];
  for (let c = 0; c < numCourses; c++) {
    if (indegree[c] === 0) queue.push(c);
  }
  let taken = 0;
  for (let head = 0; head < queue.length; head++) {
    taken++;
    for (const next of graph[queue[head]]) {
      indegree[next]--;
      if (indegree[next] === 0) queue.push(next);
    }
  }
  return taken === numCourses;
}

Say the reduction out loud first: "courses are nodes, prerequisites are directed edges, and the answer is whether the graph is acyclic." Interviewers want to hear that you recognized the graph problem before you pick an algorithm.

Either DFS with colors or Kahn's algorithm is a full-credit answer. Kahn's is often easier to get right under pressure because it's iterative and the final check is a single count comparison. Walk through a three-node cycle to show that its courses never enter the queue.