Course Schedule

The problem

There are n courses, numbered 0 to n - 1. Each pair in prerequisites is [course, prerequisite]: the second course must be finished before the first can be taken. Return true if every course can be finished in some order, and false if not. n can be 0, and then the answer is true. A course may appear in no pair at all. A pair may name one course twice, such as [1, 1]; that course can never be taken.

What to write

function solve(n: number, prerequisites: number[][]): boolean

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

Output
true

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

Output
false

Constraints

0–200 courses; valid directed prerequisite pairs.

Hints

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

1. Hint 1: Use the constraints

   There are at most 200 courses, so speed is not the hard part. The hard part is saying exactly what makes a set of pairs impossible. Notice what the input allows: n can be 0, a course can appear in no pair at all, and a pair such as [1, 1] makes a course its own prerequisite.

2. Hint 2: Ask a smaller question

   Take three courses: course 1 needs course 0, and course 2 needs course 1. Which course can you take first, and what makes it the one? Which course becomes possible after that? Now add the pair [0, 2] and ask the first question again.

3. Hint 3: Name the pattern

   Finding an order in which everything comes after the things it needs is called topological ordering. The signal is pairs that say one thing must come before another. Such an order exists unless the requirements form a cycle: a chain that leads back to where it started. This problem only asks whether an order exists. Read the lesson on topological ordering.

4. Hint 4: State the invariant

   For every course, keep a count of its prerequisites that are not taken yet. A course is ready exactly when its count is 0, and taking a course lowers the count of every course that needs it. Courses on a cycle wait for each other, so their counts never reach 0.

5. Hint 5: Sketch the pseudocode

   For each pair [course, prerequisite]: add course to prerequisite's list and 1 to course's count. Put every course with count 0 in a queue, a waiting line. While it is not empty: take one, add 1 to taken, lower the count of each course on its list, and queue those that reach 0. Return whether taken equals n.

Solution

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

Approach

Count incoming prerequisites and queue courses with none. Remove each queued course’s outgoing edges; all courses can be completed only if all enter the queue.

The slow way

Keep a note of which courses are taken. Scan all the courses again and again, and take any course whose prerequisites are all taken already. Stop when a whole scan takes nothing, and answer true if every course got taken. It is correct, but each scan rereads all the pairs, and a long chain of courses can need about n scans.

The insight

A course can be taken as soon as none of its prerequisites is missing, and taking it may free other courses. Keep taking free courses. If every course gets taken, an order exists. If some are left, each of them waits for a course that is also left, so the requirements form a cycle: a chain that leads back to where it started.

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 taking a course 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 has nothing in its way and can be taken now. If no such course exists, nothing can ever start.
3. Take the course at the front of the queue and count it. Every course in the queue is ready, so taking the front one is always allowed. The number of courses taken is what the answer is read from at the end.
4. Each course that needs it now waits for one course fewer. The course taken was one of their prerequisites and is now finished. Lowering their counts keeps each count equal to the number of prerequisites still missing.
5. A course that waits for nothing more joins the queue. A count of 0 means the last missing prerequisite has been taken, so the course is ready. The count reaches 0 only once, so a course joins the queue only once.
6. Return true only if every course was taken. A course on a cycle waits for a course on that same cycle, so its count never reaches 0 and it is never taken. When the number taken equals n, nothing was held back.

The same numbered steps are the comments in each solution.

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

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

from collections import deque


def solve(n, prerequisites):
    # 1. For each course, note which courses need it and how many it needs
    dependents = [[] for _ in range(n)]
    indegree = [0] * n
    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(n) if indegree[i] == 0)
    # 3. Take the course at the front of the queue and count it
    taken = 0
    while queue:
        course = queue.popleft()
        taken += 1
        # 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 true only if every course was taken
    return taken == n

Example 1, traced

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

Output
true

Why it works

A course's count always equals the number of its prerequisites not taken yet, so a course joins the queue exactly when it becomes possible. Without a cycle, as long as courses are left, one of them has a count of 0, so all n get taken. On a cycle every course waits for a course of that cycle, none reaches 0, and fewer than n are taken.

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 and counts 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

• Compare the number taken with n. The queue is empty at the end of every run, so an empty queue proves nothing: in example 2 it is empty from the start, nothing is taken, and the answer is false.
• Queue a course only when its count reaches 0, not on every drop. With 4 courses and pairs [1, 0], [2, 0], [3, 1], [3, 2], course 3 is queued twice, 5 are counted, and the answer is false.
• A pair is [course, prerequisite], so the second course comes first. Add 1 to the count of the first course, the one that waits. Counting on the prerequisite instead makes example 1 return false.

Pattern

Topological ordering. Builds on Rotting Oranges.

Keep going