Course Schedule II

MediumGraphsDFSBFSGraphTopological Sort

Problem

You are given a number of courses and a list of prerequisite pairs, where each pair says one course must be completed before another. Return one valid order in which all courses can be taken, or an empty list if no such order exists because the prerequisites are contradictory.

Example. With a single prerequisite pair saying course 1 requires course 0, a valid order is [0, 1]; if the pairs instead form a cycle, the answer is an empty list.

Key idea

This extends the yes-or-no cycle check from Course Schedule into actually constructing an ordering. One approach, Kahn's algorithm, repeatedly finds courses with no outstanding prerequisites (nodes with in-degree zero), takes one, appends it to the result, and decrements the in-degree of every course that depended on it; this can surface new zero-prerequisite courses, so it keeps going until no more can be taken. If the result ends up shorter than the total number of courses, some courses were stuck behind each other in a cycle and never became available, so the answer is empty. An alternative is depth-first search: after fully exploring everything a course depends on, push that course onto a stack, then read the stack back to front, since a course can only finish after all of its dependencies have already finished, which is exactly what a reversed postorder guarantees.

Solution

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array<number>(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }

  const queue: number[] = [];
  for (let course = 0; course < numCourses; course++) {
    if (inDegree[course] === 0) {
      queue.push(course); // no outstanding prerequisites, so it can be taken first
    }
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const course = queue.shift() as number;
    order.push(course);

    for (const next of graph[course]) {
      inDegree[next]--; // one fewer prerequisite left for this dependent course
      if (inDegree[next] === 0) {
        queue.push(next);
      }
    }
  }

  return order.length === numCourses ? order : []; // shorter order means a cycle stalled some courses
}

Complexity

  • Time: O(V + E). Building the graph and visiting every node and edge once.
  • Space: O(V + E). For the adjacency list, in-degree counts or recursion state, and the output order.

Watch out for

  • With depth-first search, track "in progress" versus "finished" states, just as in Course Schedule, to detect and bail out on cycles.
  • With Kahn's algorithm, comparing the final order's length against the total course count replaces explicit cycle tracking.
  • Several valid orderings can exist; any one that respects every prerequisite pair is acceptable.

Pattern

This is topological sort, the general technique for sequencing tasks under precedence constraints, built on the same graph and cycle-awareness as Course Schedule but extended to emit the order itself.

Related questions