Problem overview
The method findOrder(numCourses, prerequisites) receives the number of courses, labelled 0 to numCourses - 1, and a list of pairs. A pair [a, b] means course b must be taken before course a. The method returns an order in which all the courses can be taken, as an array of course numbers. A course is ready when all its prerequisites have been taken. Whenever several courses are ready, the one with the smallest number comes next, which makes the order unique. If taking all the courses is impossible, it returns an empty array.
With numCourses = 4 and prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]], only course 0 is ready at first. After it, courses 1 and 2 are both ready and 1 is smaller, then comes 2, and course 3 is ready last. The answer is [0, 1, 2, 3]. The order [0, 2, 1, 3] respects every prerequisite too, but it takes 2 while the smaller course 1 is ready, so it is not the answer.
With prerequisites = [[1, 0], [2, 1], [1, 2]] on three courses, courses 1 and 2 wait for each other, a cycle, so neither can ever be taken. The answer is [].
Approach: Kahn's algorithm, with a min-heap instead of a queue
Draw each pair [a, b] as an arrow from b to a, from the course to take first to the course that needs it. Kahn's algorithm repeatedly takes a course that has no untaken prerequisites, then removes its arrows, so the courses after it get one prerequisite closer to ready.
It needs two pieces of data. graph[b] lists the courses that wait for course b. inDegree[a] counts the prerequisites of course a that are not taken yet (the in-degree is the number of arrows pointing into it). A course is ready when its count is 0.
The usual version keeps the ready courses in a queue. Here the smallest ready course must come first, so they wait in a min-heap, which always hands back its smallest value. The lesson's starter code loads a library whose algorithms.DataStructures.Heap.MinHeap has insert(value), extract() (removes and returns the smallest value) and isEmpty(). Each insert and extract costs O(log V).
If fewer than numCourses courses get taken, the rest wait on a cycle, or on a course that does. Their counts never reach 0, so they never enter the heap, and no order exists.
Here is the setup for numCourses = 5 and prerequisites = [[1, 4], [0, 4], [2, 3]]:
graph [[],[],[],[2],[1,0]]
inDegree [1,1,1,0,0]
Courses 3 and 4 have count 0, so they start in the heap. The run takes 3 first (the smaller). That frees course 2, so the heap holds 2 and 4, and 2 is taken. Then 4 is taken, which frees courses 1 and 0, and the smaller one, 0, comes first. The result is [3, 2, 4, 0, 1].
A plain linear scan for the smallest ready course before every pick would cost O(V²) instead.
Step by step
- Build
graphwithArray.from({length: numCourses}, () => []): one empty array per course. - Build
inDegreeasnumCourseszeros, withnew Array(numCourses).fill(0). - Loop over
prerequisiteswithfor...of. Each pair becomes one arrow. - Record the arrow: push
prereq[0]ontograph[prereq[1]]. Courseprereq[1]comes first, andprereq[0]waits for it. - Count the prerequisite: do
inDegree[prereq[0]]++. When the loop ends,inDegree[a]is the number of pairs[a, b]in the input. - Create
ready, a newMinHeap, to hold the courses that can be taken now. - Seed the heap: loop over every course, and
inserteach one whoseinDegreeis 0. The courses that need nothing are where any valid order starts. - Create
order, an empty array for the courses in the order they are taken. - Loop while the heap is not empty, with
!ready.isEmpty(). Each course enters the heap at most once, so this runs at most once per course. - Take the smallest ready course with
ready.extract(), and push it ontoorder. This is the key line: all of its prerequisites are taken, so taking it now is safe. - Release the waiting courses: for each
nextCourseingraph[course], doinDegree[nextCourse]--. - Queue the newly ready ones: if the count reaches 0,
insertnextCourseinto the heap. A count reaches 0 only once, so no course is inserted twice. - After the loop, return
[]iforder.length < numCourses, andorderotherwise.
The solution in JavaScript
var algorithms = require('algorithms')
class Solution {
findOrder(numCourses, prerequisites) {
const graph = Array.from({length: numCourses}, () => []);
const inDegree = new Array(numCourses).fill(0);
for (const prereq of prerequisites) {
graph[prereq[1]].push(prereq[0]);
inDegree[prereq[0]]++;
}
const ready = new algorithms.DataStructures.Heap.MinHeap();
for (let course = 0; course < numCourses; course++) {
if (inDegree[course] === 0) {
ready.insert(course);
}
}
const order = [];
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;
}
}
The JavaScript details worth knowing:
- The library line. JavaScript has no built-in heap, so the lesson uses a library. The starter code already contains the
requireline, so there is nothing to add in the editor. In a project of your own, the package has to be installed first. - One array per course.
new Array(numCourses).fill([])would put the same array object in every slot, so every course would share one list of waiting courses. The arrow function passed toArray.fromruns once per index and makes a separate array each time. With the shared version, a push tobad[0]on three slots shows up as[[7],[7],[7]]. fill(0)is safe for numbers. Numbers are copied by value, so every slot ofinDegreeis independent.- The heap holds plain numbers. The values are course numbers, and a min-heap of numbers hands back the smallest one first, which is exactly the rule in the statement.
- Increment and decrement on elements.
inDegree[prereq[0]]++changes the stored number in place.
Complexity
Let V be numCourses and E the number of pairs.
Time: O((V + E) log V). Building the graph takes 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.
Space: O(V + E). The graph holds V lists and E entries, inDegree and order hold V numbers each, and the heap never holds more than V courses.
Edge cases and common mistakes
- No prerequisites.
findOrder(3, [])returns[0, 1, 2], andfindOrder(1, [])returns[0]. All courses are ready at the start, and the heap hands them out smallest first. - A cycle.
findOrder(2, [[0, 1], [1, 0]])returns[]: no course has count 0, so the heap starts empty andorderstays shorter thannumCourses. A cycle in only a part of the graph also gives[], because the courses on it, and those that need them, are never taken. - Reversed arrows. In
[a, b]the course to take first isb. Putting the arrow the other way round gives a valid-looking but wrong order. - Using a plain queue. A first-in, first-out queue gives a valid order, but not always the one with the smallest ready course first.
- Inserting a course twice. Testing
inDegree[nextCourse] === 0right after the decrement means a course is inserted exactly when its last prerequisite is taken, never again. - Returning a partial order. When some courses are stuck,
orderis not empty, but the answer must be. The length check handles that.
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 = 2,prerequisites = [[0, 1], [1, 0]]gives[].
