Course Schedule II

A programme offers numCourses courses, numbered 0 to numCourses - 1. Each entry prerequisites[i] = [a, b] means course b must be completed before you can start course a.

Return a list containing every course exactly once, in an order in which you could actually take them all while respecting every prerequisite. If several orders work, return any one of them. If it is impossible to finish all the courses (because some requirements depend on each other in a loop), return an empty list [].

Example 1

Example 2

Example 3

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses · (numCourses - 1)
• 0 <= a, b < numCourses and a != b
• All pairs [a, b] are distinct.

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

Start simple

Try permutations of the courses until one satisfies every prerequisite: O(n!·(n + E)) time.

The key idea

Treat courses as nodes and each prerequisite [a, b] as a directed edge b → a. A valid plan is a topological order of this graph: every edge points from earlier to later.

Kahn's algorithm builds one greedily. Track each course's number of unmet prerequisites (its in-degree). Every course with in-degree 0 can be taken now, so put them in a queue. Take a course from the queue, append it to the answer, and decrement the in-degree of every course it unlocks; any that drop to 0 join the queue. Taking a ready course never blocks anything else, so this greedy choice is always safe.

If the graph has a cycle, the courses on it each wait for another course on the cycle, so none of them ever reaches in-degree 0. The queue runs dry early and the answer is shorter than numCourses: that is the signal to return []. A DFS that emits courses in reverse post-order (with a "currently visiting" colour to detect cycles) is an equally valid alternative.

Complexity

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

Python

from collections import deque


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        unlocks = [[] for _ in range(numCourses)]  # need -> courses that require it
        missing = [0] * numCourses                 # prerequisites not yet taken
        for course, need in prerequisites:
            unlocks[need].append(course)
            missing[course] += 1

        # Kahn's algorithm: repeatedly take any course whose prerequisites are all done.
        ready = deque(c for c in range(numCourses) if missing[c] == 0)
        order = []
        while ready:
            course = ready.popleft()
            order.append(course)
            for nxt in unlocks[course]:
                missing[nxt] -= 1
                if missing[nxt] == 0:
                    ready.append(nxt)

        # Courses stuck on a cycle never become ready.
        return order if len(order) == numCourses else []

JavaScript

var findOrder = function(numCourses, prerequisites) {
  const unlocks = Array.from({ length: numCourses }, () => []); // need -> courses that require it
  const missing = new Array(numCourses).fill(0);                // prerequisites not yet taken
  for (const [course, need] of prerequisites) {
    unlocks[need].push(course);
    missing[course]++;
  }

  // Kahn's algorithm: repeatedly take any course whose prerequisites are all done.
  const order = [];
  for (let c = 0; c < numCourses; c++) if (missing[c] === 0) order.push(c);
  for (let head = 0; head < order.length; head++) {
    for (const next of unlocks[order[head]]) {
      if (--missing[next] === 0) order.push(next);
    }
  }

  // Courses stuck on a cycle never become ready.
  return order.length === numCourses ? order : [];
};

What the interviewer is checking

This tests whether you can model dependencies as a directed graph, produce a topological order, and detect cycles, which is the core of build systems and schedulers.

Mistakes to avoid

• Reversing the edge direction: [a, b] means b comes first.
• Forgetting courses with no prerequisites and no dependents; they still belong in the answer.
• Returning a partial order when a cycle exists instead of an empty list.
• In the DFS version, using a single visited flag, which cannot tell a cycle from a shared descendant.

Follow-ups to expect

• What is the minimum number of semesters if you can take any number of courses at once? (BFS level count.)
• Return the lexicographically smallest valid order. (Use a min-heap instead of a queue.)
• Is the order unique? (Queue never holds two courses at once.)

In real software

Build tools such as make and package managers order compilation and installation steps with a topological sort, and report a dependency cycle when none exists.

Practice next