Course Schedule

A program has numCourses courses, numbered from 0 to numCourses - 1. You are also given a list prerequisites, where each pair [a, b] means that course b must be completed before you can start course a.

Return true if there is some order in which you can complete every course while respecting all of the prerequisites, and false if that is impossible.

Courses that appear in no pair have no restrictions and can be taken at any time.

Example 1

Example 2

Example 3

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= a, b < numCourses and a != b
• No pair appears twice.

Pattern Path · Graphs: Ordering & Union-Find · problem 139 of 169

Start simple

Try orderings of the courses until one satisfies every prerequisite: O(n!) in the worst case.

The key idea

Draw an edge b → a for each pair [a, b]. A valid schedule is a topological order of this graph, and such an order exists exactly when the graph has no directed cycle: courses on a cycle each wait for another one on the same cycle, so none can go first.

Kahn's algorithm checks this directly by simulating the semester plan. Compute each course's in-degree (number of prerequisites). Every course with in-degree 0 can be taken immediately, so put them in a queue. Repeatedly take a course from the queue, count it as finished, and decrement the in-degree of every course that depends on it; any course that drops to 0 is now unlocked and joins the queue.

If all numCourses courses get taken, the order you took them in is a valid schedule. If the queue empties early, the remaining courses all still have an unfinished prerequisite among themselves, which means they contain a cycle. A DFS that looks for a back edge (a node reached again while it is still on the current path) gives the same answer.

Complexity

• Time: O(V + E)
• Space: O(V + E)

Python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        unlocks = [[] for _ in range(numCourses)]  # b -> courses that need b
        missing = [0] * numCourses                 # unmet prerequisites per course
        for course, before in prerequisites:
            unlocks[before].append(course)
            missing[course] += 1

        ready = deque(c for c in range(numCourses) if missing[c] == 0)
        taken = 0
        while ready:
            course = ready.popleft()
            taken += 1
            for nxt in unlocks[course]:
                missing[nxt] -= 1
                if missing[nxt] == 0:
                    ready.append(nxt)

        # Courses never taken are stuck on a cycle.
        return taken == numCourses

JavaScript

var canFinish = function(numCourses, prerequisites) {
  const unlocks = Array.from({ length: numCourses }, () => []); // b -> courses that need b
  const missing = new Array(numCourses).fill(0);                // unmet prerequisites
  for (const [course, before] of prerequisites) {
    unlocks[before].push(course);
    missing[course]++;
  }

  const ready = [];
  for (let c = 0; c < numCourses; c++) if (missing[c] === 0) ready.push(c);

  let taken = 0;
  while (taken < ready.length) {
    const course = ready[taken++];
    for (const next of unlocks[course]) {
      if (--missing[next] === 0) ready.push(next);
    }
  }

  // Courses never taken are stuck on a cycle.
  return taken === numCourses;
};

What the interviewer is checking

It tests whether you can turn a word problem into a directed graph and recognise cycle detection / topological sort as the real question.

Mistakes to avoid

• Getting the edge direction backwards: [a, b] means b comes first.
• Running DFS cycle detection with a single visited set, which reports false cycles when two paths reach the same node; you need a separate "on the current path" state.
• Forgetting courses that have no edges at all.
• Recursive DFS on long prerequisite chains can exceed the recursion limit in Python.

Follow-ups to expect

• Return one valid order of the courses? (Record the Kahn's queue order.)
• What is the minimum number of semesters? (BFS level count.)
• Can course x be taken before course y? (Reachability queries.)

In real software

Build systems, package managers and spreadsheet engines topologically sort dependencies and must report circular dependencies, exactly like this course check.

Practice next