Graph traversal · Topological sort (Kahn's algorithm)

Medium · O(V + E) time · O(V + E) space

Problem

There are numCourses courses, labelled 0 to numCourses − 1. You are given prerequisites, where prerequisites[i] = [a, b] means you must take course b before course a. Return any order in which you can take all the courses. If it is impossible, return an empty array.
Example 1 Input: numCourses = 6, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3],[5,3]] Output: [0, 1, 2, 3, 4, 5] (course 3 needs both 1 and 2; 4 and 5 need 3) Example 2 Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2],[1,3]] Output: [] (1 needs 0, 2 needs 1, 3 needs 2, and 1 needs 3: a cycle)
Constraints 1 ≤ numCourses ≤ 2000 0 ≤ prerequisites.length ≤ numCourses · (numCourses − 1) All pairs are distinct and a ≠ b. Several valid orders may exist. Any one is accepted.

Brute force

You are choosing university courses. Some courses have a prerequisite: you must finish course b before you start course a. In what order can you take all the courses?

  1. Every course appears exactly once in your list.
  2. For each rule "b before a", course b comes earlier in the list.
  3. If the rules contradict each other, return an empty list.

Draw each rule as an arrow from the prerequisite to the course it unlocks: b → a. Now a valid order is simply a list in which every arrow points forward. The first course in the list must be one with no arrow pointing into it.

The direct idea: try every possible order of the courses, and return the first one that obeys every rule.

The problem with it

There are n! orders (n × (n − 1) × … × 1), and checking each one takes a pass over all the rules. With only twelve courses that is already 479 million orders. It is far too slow.

But look at what a valid order is: a list where all arrows point forward. We do not need to search for it. We can build it from the left, one course at a time.

How to think your way to the optimal solution

At each step, which course is safe to put next?

A course is safe when it is not waiting for anything: all its prerequisites are already in the list. Count, for every course, how many prerequisites it still waits for. This count is called its in-degree (how many arrows point into it). A course with in-degree 0 is safe, because nothing it needs is missing.

So: take any safe course and put it in the list. Then cross it off. Every course it unlocked now waits for one fewer prerequisite. Any course whose count drops to 0 has just become safe, so it joins the line of safe courses. Repeat until nobody is left.

Why is it safe? A course with in-degree 0 has no prerequisite left outside the list, so placing it next can never break a rule. And if we get stuck with courses left but none safe, every remaining course is waiting on another remaining course. That means there is a loop of prerequisites, and no valid order exists.

The optimal solution

  1. Build the arrows, and count the in-degree of every course.
  2. Put every course with in-degree 0 in a queue. A queue hands out items in the order they arrived.
  3. Take a course out of the queue and add it to the answer.
  4. For each course it unlocks: subtract 1 from its in-degree. it reaches 0⟶add it to the queue
  5. Repeat from step 3 until the queue is empty. the answer has all the courses⟶return it fewer⟶there is a loop: return an empty list

By hand, with 6 courses and the rules [1,0] [2,0] [3,1] [3,2] [4,3] [5,3]. The in-degrees are: course 0 has 0, courses 1 and 2 have 1, course 3 has 2, courses 4 and 5 have 1.

  1. Only course 0 has in-degree 0. The queue is [0].
  2. Take 0. Answer [0]. It unlocks 1 and 2: both drop to 0, so both join the queue: [1, 2].
  3. Take 1. Answer [0, 1]. It unlocks 3, which drops from 2 to 1. Not safe yet.
  4. Take 2. Answer [0, 1, 2]. It unlocks 3, which drops to 0. The queue is [3].
  5. Take 3. Answer [0, 1, 2, 3]. It unlocks 4 and 5, both drop to 0: queue [4, 5].
  6. Take 4, then 5. Answer [0, 1, 2, 3, 4, 5]. That has all 6 courses, so we return it.

With the loop [1,0] [2,1] [3,2] [1,3], only course 0 starts safe. Taking it only lowers course 1 from 2 to 1, so nothing new joins the queue. We stop with 1 course in the answer, not 4, so we return [].

Press Play to watch the queue and the in-degree numbers change.

Complexity analysis

O(V + E)
Time. Here's why: V is the number of courses and E the number of rules. Building the arrows and counting in-degrees takes one pass over the E rules. Each course enters the queue once and is taken out once, which is V steps. When a course is taken out, we look at each arrow leaving it once, so over the whole run we look at each of the E arrows once.
O(V + E)
Space. The arrows take V lists holding E entries in total. The in-degree list, the queue and the answer each hold at most V courses.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"You can take as many courses at once as you like. What is the fewest number of semesters?"

What they are checkingWhether you see that the queue already holds every course that is safe to take at the same time.

A strong answerI process the queue in rounds. In each round I take out everything that is in the queue right now, and that is one semester. The courses they unlock go into the queue for the next round. The number of rounds is the number of semesters. If there is a loop, I never finish all the courses, and I return -1 (or whatever the problem asks for).

"There is a loop. Tell me which courses are the problem."

What they are checkingWhether you can read useful information out of the failure case instead of only reporting it.

A strong answerWhen the queue empties early, the courses that never reached in-degree 0 are the ones that are in a loop or wait on one. They are exactly the courses missing from the answer. To report one actual loop, I would start from one of them and keep following a prerequisite that is also in that leftover group until a course repeats. That repeated course is on a loop.

"Several courses are safe at once. Always take the one with the smallest number."

What they are checkingWhether you know why the queue gives "any valid order", and what to use when the order matters.

A strong answerA plain queue returns whichever safe course arrived first, which is a valid order but not a chosen one. To always take the smallest, I swap the queue for a min-heap. The heap hands out the smallest safe course, and unlocked courses are added to it. The rest of the algorithm stays the same. The cost goes from O(V + E) to O(V log V + E), because each heap step takes about log V.

Spot this pattern