Problem overview
There are numCourses courses, labelled 0 to numCourses - 1. Each pair [a, b] in prerequisites means course b must be taken before course a. The method findOrder returns an order in which all the courses can be taken. A course is ready when all its prerequisites have been taken, and whenever several courses are ready, the one with the smallest number is taken next. That rule makes the answer unique. If taking every course is impossible, the method returns an empty array.
For numCourses = 4 and prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] the answer is [0, 1, 2, 3]. Only course 0 is ready at first. After it, courses 1 and 2 are both ready and 1 comes first. Course 3 is ready once both 1 and 2 are taken. For numCourses = 5 and prerequisites = [[1, 4], [0, 4], [2, 3]] the answer is [3, 2, 4, 0, 1]. For [[1, 0], [2, 1], [1, 2]] with three courses it is []: courses 1 and 2 wait for each other.
Approach: Kahn's algorithm, with a heap of ready courses
Think of each pair [a, b] as an arrow from b to a, from the course to take first to the course that needs it. For every course, keep its in-degree: the number of its prerequisites that haven't been taken yet. A course with in-degree 0 is ready. Taking a course removes its outgoing arrows, which lowers the in-degree of every course that waits for it by one, and a course whose count reaches 0 becomes ready.
This is Kahn's algorithm for a topological order. The usual version keeps the ready courses in a queue. Here the order must pick the smallest ready course every time, so they wait in a min-heap instead, which gives the smallest value in O(log V). With a plain queue the answer to the second example would be [3, 4, 2, 1, 0], which is a valid order but takes 4 while the smaller course 2 is ready.
If fewer than numCourses courses get taken at the end, the remaining ones wait on a cycle, or on a course that does. Courses on a cycle never reach in-degree 0, so they never enter the heap, and neither does any course that needs one of them. No order exists then.
For the second example the setup gives these lists of waiting courses (index is the course) and in-degrees:
graph: [[], [], [], [2], [1, 0]]
inDegree: [1, 1, 1, 0, 0]
Courses 3 and 4 start in the heap. The run takes 3 (course 2 becomes ready), then 2, then 4 (courses 1 and 0 become ready), then 0 and 1: the order [3, 2, 4, 0, 1].
Step by step
- Build
graphas anumber[][]with one empty array per course:Array.from({length: numCourses}, () => []).graph[b]will hold the courses that wait for courseb. - Create
inDegreewithnumCourseszeros.inDegree[a]counts the prerequisites ofanot yet taken. - Loop over
prerequisiteswithfor...of. Each pair becomes one arrow. - Push
prereq[0]ontograph[prereq[1]]: courseprereq[1]comes first, andprereq[0]waits for it. - Add 1 to
inDegree[prereq[0]]. That course has one more prerequisite. - Create the heap
readywithnew MinHeap(). The lesson provides this class, withinsert,extract(removes and returns the smallest value),peek,sizeandisEmpty. - Loop over every course from 0 to
numCourses - 1. - Insert the free courses: if
inDegree[course] === 0, insert it. These are where any valid order can start. If there are none, every course waits for another and nothing can be taken. - Create
order, an emptynumber[]for the courses in the order they are taken. - Loop while the heap isn't empty:
while (!ready.isEmpty()). - Take the smallest ready course with
ready.extract(). This is the key line: all its prerequisites are taken, and it is the smallest such course. - Push it onto
order. - Visit the courses that wait for it,
graph[course], withfor...of. - Subtract 1 from
inDegree[nextCourse]: one of its prerequisites is now taken. - Insert it if its count is 0. A count reaches 0 only once, so each course enters the heap at most once.
- After the loop, check the length. If
order.length < numCourses, return[]. - Otherwise return
order.
The solution in TypeScript
class Solution {
findOrder(numCourses: number, prerequisites: number[][]): number[] {
const graph: number[][] = Array.from({length: numCourses}, () => []);
const inDegree: number[] = new Array(numCourses).fill(0);
for (const prereq of prerequisites) {
graph[prereq[1]].push(prereq[0]);
inDegree[prereq[0]]++;
}
const ready = new MinHeap();
for (let course = 0; course < numCourses; course++) {
if (inDegree[course] === 0) {
ready.insert(course);
}
}
const order: number[] = [];
while (!ready.isEmpty()) {
const course = ready.extract();
order.push(course);
for (const nextCourse of graph[course]) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] === 0) {
ready.insert(nextCourse);
}
}
}
if (order.length < numCourses) {
return [];
}
return order;
}
}
A few TypeScript details:
- One array per course. The arrow function in
Array.fromruns once per index, so every course gets its own empty array.new Array(numCourses).fill([])would put one shared array in every slot: pushing a course to one list would add it to all of them. - Annotations are erased.
number[][]and the other types are checked by the compiler only. The compiled JavaScript has no types, and the lesson'sMinHeapis an ordinary class there. - Two
coursevariables. Theforloop'slet courseand theconst courseinside thewhileloop are separate variables in separate blocks, so they don't clash. inDegree[prereq[0]]++changes a number inside the array in place, which is allowed on aconstarray.
Complexity
Time: O((V + E) log V), where V is numCourses and E the number of pairs. Building the graph costs O(V + E). Each course is inserted into the heap and extracted once, at O(log V) each, and each pair is looked at once, when its first course is taken. Picking the smallest ready course by scanning all courses before every step would cost O(V²) instead.
Space: O(V + E). The graph holds one entry per pair and one list per course, and inDegree, the heap and order each hold at most V numbers.
Edge cases and common mistakes
- No prerequisites. With
numCourses = 3and an empty list, every course is ready and the answer is[0, 1, 2]. A single course gives[0]. - A cycle.
[[0, 1], [1, 0]]with two courses leaves the heap empty from the start, so the answer is[]. A cycle among some courses also blocks every course that needs one of them, even when other courses could be taken. - Reversing the pair.
[a, b]meansbcomes first. Storing the arrow the other way round, fromatob, treatsaas the course to take first. For[[0, 2]]with three courses the correct answer is[1, 2, 0], but that mistake produces[0, 1, 2], which takes course 0 before its prerequisite. - Using a queue instead of the heap. The order is still valid but no longer the smallest-first one, as the second example shows.
- Returning a partial order. When a cycle exists, the method must return
[], not the courses taken before the cycle blocked everything. That is what the final length check does. - Counting prerequisites wrongly. Add to
inDegree[prereq[0]], the course that waits, not toinDegree[prereq[1]].
Testing
numCourses = 4,prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]gives[0, 1, 2, 3].numCourses = 5,prerequisites = [[1, 4], [0, 4], [2, 3]]gives[3, 2, 4, 0, 1].numCourses = 3,prerequisites = [[1, 0], [2, 1], [1, 2]]gives[].numCourses = 3,prerequisites = []gives[0, 1, 2].numCourses = 3,prerequisites = [[0, 2]]gives[1, 2, 0].
