Course Schedule II

The problem

There are numCourses courses, numbered 0 to numCourses - 1. Each pair in prerequisites is [course, prerequisite]: the second course must be finished before the first can be taken. Return a list of all the courses in an order in which they can be taken. When several orders work, any one of them is accepted. When no order works, because some courses wait for each other, return an empty list.

What to write

function solve(numCourses: number, prerequisites: number[][]): number[]

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

Output
[0,1]

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

Output
[0,1,2,3]

Constraints

Course IDs range from 0 to numCourses-1.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Several orders can be right, and any one of them is accepted, so you are not looking for one special order. The only rule is that no course comes before something it needs. When some courses wait for each other no order exists, and the answer is an empty list.

2. Hint 2: Ask a smaller question

   Look at example 2: courses 1 and 2 need course 0, and course 3 needs both 1 and 2. Which course has to be written first? Once it is written, which courses could come next? What is true of a course at the moment you may write it down?

3. Hint 3: Name the pattern

   Writing things in an order where everything comes after the things it needs is topological ordering. The signal is pairs that say one thing must come before another, plus a request for the order itself. Build the order front to back: the next course is always one whose prerequisites are all written down already. Read the lesson on topological ordering.

4. Hint 4: State the invariant

   The order built so far is always valid: every course in it comes after all its prerequisites. Give each course a count of its prerequisites not yet in the order, and add a course only when that count is 0. Courses on a cycle, a chain of requirements that leads back to its start, never reach 0.

5. Hint 5: Sketch the pseudocode

   For each pair [course, prerequisite]: put course on prerequisite's list and add 1 to course's count. Line up every course with count 0 in a queue. Until it is empty: move the front course to the order, lower the count of each course on its list, queue those that reach 0. Return the order if complete, otherwise an empty list.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Process courses with zero incoming prerequisites, removing their outgoing edges. Unprocessed courses indicate a cycle.

The slow way

Write down every possible arrangement of the courses and return the first one in which every prerequisite comes before its course. If none passes, return an empty list. It is correct, but the number of arrangements explodes: 9 courses can be arranged in 362,880 ways, and each one may have to be checked against the pairs.

The insight

The first course of any valid order must be one that needs nothing. Once it is written down, courses that needed only that course become free too. So build the order front to back, always writing a course whose prerequisites are all written already. If you get stuck with courses left over, they wait for each other in a cycle, a chain of requirements that leads back to its start.

Step by step

1. For each course, note which courses need it and how many it needs. Each pair is stored on the prerequisite's side, so adding a course to the order leads straight to the courses that wait for it. The count is the number of prerequisites a course still misses.
2. Put every course that needs nothing in a queue. A queue is a line: you add at the back and take from the front. A course whose count is 0 needs nothing before it, so it may come next. Any valid order has to start with such a course.
3. Take the course at the front of the queue and add it to the order. Every course in the queue has all its prerequisites in the order already, so adding it keeps the order valid. Which ready course goes first does not matter, because any valid order is accepted.
4. Each course that needs it now waits for one course fewer. The course added to the order was one of their prerequisites. Lowering their counts keeps each count equal to the number of prerequisites not yet in the order.
5. A course that waits for nothing more joins the queue. A count of 0 means its last missing prerequisite was added to the order, so the course may follow. The count reaches 0 only once, so a course joins the queue, and the order, only once.
6. Return the order if it holds every course, otherwise an empty list. Courses on a cycle wait for each other and are never added. A short order therefore means no valid order exists, and the problem asks for an empty list then, not for the part that was collected.

The same numbered steps are the comments in each solution.

function solve(numCourses, prerequisites) {
  // 1. For each course, note which courses need it and how many it needs
  const next = Array.from({ length: numCourses }, () => []),
    degree = Array(numCourses).fill(0);
  // a is the course and b is its prerequisite: b has to come first.
  for (const [a, b] of prerequisites) {
    next[b].push(a);
    degree[a]++;
  }
  // 2. Put every course that needs nothing in a queue
  const q = [];
  for (let i = 0; i < numCourses; i++) if (!degree[i]) q.push(i);
  // 3. Take the course at the front of the queue and add it to the order
  const order = [];
  // Removing the first item of an array is slow, so nothing is removed:
  // i is the position of the front of the queue, and push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const course = q[i];
    order.push(course);
    // 4. Each course that needs it now waits for one course fewer
    for (const n of next[course]) {
      degree[n]--;
      // 5. A course that waits for nothing more joins the queue
      if (degree[n] === 0) q.push(n);
    }
  }
  // 6. Return the order if it holds every course, otherwise an empty list
  return order.length === numCourses ? order : [];
}

function solve(numCourses: number, prerequisites: number[][]): number[] {
  // 1. For each course, note which courses need it and how many it needs
  const next: number[][] = Array.from({ length: numCourses }, () => []),
    degree = Array(numCourses).fill(0);
  // a is the course and b is its prerequisite: b has to come first.
  for (const [a, b] of prerequisites) {
    next[b].push(a);
    degree[a]++;
  }
  // 2. Put every course that needs nothing in a queue
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (!degree[i]) q.push(i);
  // 3. Take the course at the front of the queue and add it to the order
  const order: number[] = [];
  // Removing the first item of an array is slow, so nothing is removed:
  // i is the position of the front of the queue, and push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const course = q[i];
    order.push(course);
    // 4. Each course that needs it now waits for one course fewer
    for (const n of next[course]) {
      degree[n]--;
      // 5. A course that waits for nothing more joins the queue
      if (degree[n] === 0) q.push(n);
    }
  }
  // 6. Return the order if it holds every course, otherwise an empty list
  return order.length === numCourses ? order : [];
}

from collections import deque


def solve(numCourses, prerequisites):
    # 1. For each course, note which courses need it and how many it needs
    dependents = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, prerequisite in prerequisites:
        dependents[prerequisite].append(course)
        indegree[course] += 1
    # 2. Put every course that needs nothing in a queue
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque(i for i in range(numCourses) if indegree[i] == 0)
    # 3. Take the course at the front of the queue and add it to the order
    order = []
    while queue:
        course = queue.popleft()
        order.append(course)
        # 4. Each course that needs it now waits for one course fewer
        for dependent in dependents[course]:
            indegree[dependent] -= 1
            # 5. A course that waits for nothing more joins the queue
            if indegree[dependent] == 0:
                queue.append(dependent)
    # 6. Return the order if it holds every course, otherwise an empty list
    return order if len(order) == numCourses else []

Example 2, traced

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

Output
[0,1,2,3]

Why it works

A course joins the queue only when its count is 0, which means all its prerequisites are in the order already. So every course lands after everything it needs, and the order is valid. A course that is never added waits for a course that is never added either, which can only happen when a cycle exists. Then no valid order exists.

Time and space

Time O(V + E), extra space O(V + E). With V courses and E pairs: each pair is read once to build the lists and at most once more when its prerequisite is taken, and each course is queued at most once. That is O(V + E) time. The lists, counts and order take O(V + E) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Check that the order holds every course before returning it. A cycle can block only some courses while the rest are still collected: 3 courses with pairs [1, 2], [2, 1] give [0], but the answer is an empty list.
• Store each pair from the prerequisite's side: the second course's list gets the first course. Read the other way round, every pair is turned around, the order comes out backwards, and example 1 returns [1, 0].
• Queue a course only when its count reaches 0. Queued on every drop, course 3 of example 2 enters the order twice. The order then has 5 entries for 4 courses, so an empty list is returned.

Pattern

Topological ordering. Builds on Course Schedule.

Keep going