Course Schedule II

Examples

Input: numCourses = 2, prerequisites = [[1, 0]]
Output: [0, 1]

Course 0 has no prerequisites, so it goes first; course 1 needs course 0 first.

Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]

0 has no prerequisites, 1 and 2 only need 0, and 3 needs both 1 and 2. [0, 2, 1, 3] would also be accepted.

Input: numCourses = 1, prerequisites = []
Output: [0]

A single course with no prerequisites can always be taken.

Constraints

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= numCourses × (numCourses - 1)

• There are no duplicate prerequisite pairs.

Approach

Think of each course's in-degree as "how many prerequisites does it still need before it's takeable." A course can be added to the order the moment its in-degree hits zero.

Start by finding every course whose in-degree is already zero - those can go first. As each course gets added to the order, "remove" it from the graph by decreasing the in-degree of every course that depends on it. Any course whose in-degree drops to zero is now takeable, so it joins the pool of next candidates. Keep repeating this until no more courses can be taken.

If every course eventually gets added, the resulting order is valid. If some courses are left over with in-degree still above zero, they're stuck in a cycle with each other - it's impossible, so return []. This peeling process is exactly Kahn's algorithm for topological sorting, and it can be driven with a simple queue.

Solutions

Brute Force - Round-by-Round Simulation

Repeatedly scan all not-yet-taken courses; in each pass, take every course whose prerequisites have all already been taken. If a full pass takes nothing new, the remaining courses are stuck in a cycle, so stop.

function findOrder(numCourses, prerequisites) {
  const taken = new Array(numCourses).fill(false);
  const order = [];

  const prereqsOf = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) {
    prereqsOf[a].push(b);
  }

  while (order.length < numCourses) {
    let takenSomething = false;

    for (let course = 0; course < numCourses; course++) {
      if (taken[course]) continue;
      if (prereqsOf[course].every((p) => taken[p])) {
        taken[course] = true;
        order.push(course);
        takenSomething = true;
      }
    }

    if (!takenSomething) break; // remaining courses are stuck in a cycle
  }

  return order.length === numCourses ? order : [];
}

Time: O(V × (V + E)) - up to V passes, each scanning every course and its prerequisites · Space: O(V + E)

Optimal - BFS / Kahn's Algorithm

Compute each course's in-degree, seed a queue with every course that already has in-degree zero, then repeatedly pop a course, append it to the order, and decrease the in-degree of its dependents - pushing any that reach zero. If the final order includes every course, it's valid.

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

  for (const [a, b] of prerequisites) {
    graph[b].push(a); // b unlocks a
    inDegree[a]++;
  }

  const queue = [];
  for (let course = 0; course < numCourses; course++) {
    if (inDegree[course] === 0) queue.push(course);
  }

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

    for (const next of graph[course]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }

  return order.length === numCourses ? order : [];
}

Time: O(V + E) - every course is queued once and every edge is relaxed once · Space: O(V + E)