Problem overview
There are numCourses courses, labeled 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, as an ArrayBuffer[Int], or an empty ArrayBuffer if that is impossible. A course is ready when all its prerequisites are taken, and whenever several are ready, the smallest number comes next. That rule makes the answer unique.
In the first example, numCourses = 4 and the pairs are [1, 0], [2, 0], [3, 1], [3, 2]. Only course 0 is ready at first. Taking it makes 1 and 2 ready, and 1 comes first. Course 3 is ready once both are taken. The answer is [0, 1, 2, 3]. The order 0, 2, 1, 3 also respects every prerequisite, but it takes 2 while the smaller 1 is ready.
In the third example, [[1, 0], [2, 1], [1, 2]], courses 1 and 2 wait for each other. That is a cycle, so not every course can be taken, and the answer is empty.
Approach: Kahn's algorithm with a min-heap
Treat each pair [a, b] as an arrow from b to a, from the course to take first to the course that needs it. Count, for each course, how many prerequisites are still untaken. This count is its in-degree, the number of arrows pointing into it. A course with count 0 is ready.
Kahn's algorithm repeats one move: take a ready course, then remove its outgoing arrows. Every course that was waiting for it gets one prerequisite closer, and when a count reaches 0, that course becomes ready. If the ready courses waited in an ordinary queue, any valid order would come out. Here the smallest ready course must always be next, so they wait in a min-heap (a priority queue that gives back the smallest value first).
If fewer than numCourses courses get taken, the rest are stuck. They are on a cycle, or they need a course that is. Their counts never reach 0, so they never enter the heap, and no order exists.
Looking through all the courses for the smallest ready one before each pick would cost O(V^2) for V courses. The heap makes each pick O(log V).
For the first example, the lesson's data structures end up as follows after the pairs are read. graph lists, for each course, the courses waiting for it, and inDegree is the count per course:
ArrayBuffer(1, 2) ArrayBuffer(3) ArrayBuffer(3) ArrayBuffer()
0 1 1 2
Only course 0 has a count of 0, so the heap starts with just 0.
Step by step
- Build the graph:
graphis an array ofnumCoursesemptymutable.ArrayBuffer[Int]s, made withArray.fill(numCourses)(...).graph(b)will hold the courses that wait for courseb.Array.fillevaluates its second argument once per entry, so each course gets its own buffer. - Create
inDegree, anArray[Int]ofnumCourseszeros.inDegree(a)counts the prerequisites ofathat are not taken yet. - Loop over the pairs with
prereq <- prerequisites. Each pair becomes one arrow. - Add the arrow: append
prereq(0)tograph(prereq(1))with+=. Courseprereq(1)comes first, andprereq(0)waits for it. - Count the prerequisite: add 1 to
inDegree(prereq(0))with+= 1. Scala has no++operator. - Create the heap
ready, amutable.PriorityQueue[Int]()(Ordering[Int].reverse). A ScalaPriorityQueuegives back its largest value first, and the reversed ordering turns it into a min-heap. - Find the starting courses. Loop over
course <- 0 until numCoursesand, ifinDegree(course) == 0, enqueue it intoready. Courses that need nothing are where every valid order starts. - Create
order, an emptyArrayBuffer[Int](). Its length also counts the courses taken so far. - Loop while
ready.nonEmpty. Each course enters the heap at most once, so this runs at most once per course. - Take the smallest ready course with
dequeue()intocourse. This is the key line: all its prerequisites are taken, so it is safe, and it is the smallest such course. - Record it with
order += course. - Update the waiting courses. Loop over
nextCourse <- graph(course), and subtract 1 frominDegree(nextCourse): one of its prerequisites is now taken. - Release the ready ones. If
inDegree(nextCourse)reached 0, enqueuenextCourseintoready. A count reaches 0 only once, so no course enters the heap twice. - Detect a cycle. After the loop, if
order.length < numCourses, return an emptyArrayBuffer[Int](). - Finish with
orderas the last expression.
The solution in Scala
class Solution {
def findOrder(numCourses: Int, prerequisites: Array[Array[Int]]): ArrayBuffer[Int] = {
val graph = Array.fill(numCourses)(mutable.ArrayBuffer[Int]())
val inDegree = Array.fill(numCourses)(0)
for (prereq <- prerequisites) {
graph(prereq(1)) += prereq(0)
inDegree(prereq(0)) += 1
}
val ready = mutable.PriorityQueue[Int]()(Ordering[Int].reverse)
for (course <- 0 until numCourses) {
if (inDegree(course) == 0) {
ready.enqueue(course)
}
}
val order = ArrayBuffer[Int]()
while (ready.nonEmpty) {
val course = ready.dequeue()
order += course
for (nextCourse <- graph(course)) {
inDegree(nextCourse) -= 1
if (inDegree(nextCourse) == 0) {
ready.enqueue(nextCourse)
}
}
}
if (order.length < numCourses) {
return ArrayBuffer[Int]()
}
order
}
}
The Scala details worth a closer look:
- Imports. The code uses both
mutable.and a bareArrayBuffer, which the lesson already makes available. In a file of your own, addimport scala.collection.mutableandimport scala.collection.mutable.ArrayBuffer. Array.filland shared buffers.Array.fill(3)(ArrayBuffer[Int]())builds three separate buffers, because the expression is evaluated for each entry. If you create one buffer first and pass the name, as inArray.fill(3)(buf), all three entries are the same buffer. Appending 9 to the first makes all of them showArrayBuffer(9), and every course would appear to wait for every other.- The reversed ordering.
mutable.PriorityQueue[Int]()alone dequeues the largest value first. After enqueueing 3, 1 and 2, the plain queue gives back 3 and the reversed one gives back 1. The second pair of parentheses inPriorityQueue[Int]()(Ordering[Int].reverse)passes the ordering explicitly. +=on an element and on a buffer.graph(a) += xappends to the buffer stored at indexa.inDegree(a) += 1adds to anIntstored in an array slot. For anIntslot, Scala rewrites it asinDegree(a) = inDegree(a) + 1.order.length. AnArrayBufferreports its size withlength(orsize), so no separate counter is needed.- The return type. The method returns an
ArrayBuffer[Int], so an empty result is a new empty buffer. Printing it showsArrayBuffer().
Complexity
Time: O((V + E) log V), where V is numCourses and E the number of pairs. Building the graph looks at each pair once. Each course is pushed to the heap and popped from it at most 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 one entry per pair, and the counts, the heap and the result hold at most one entry per course.
Edge cases and common mistakes
- No prerequisites. With
numCourses = 3and no pairs, every course is ready at once, and the answer is[0, 1, 2]. With one course, it is[0]. - A cycle of two.
numCourses = 2with[0, 1]and[1, 0]gives an empty buffer: no course is ever ready. - A cycle that doesn't block everything. In the third example, course 0 is taken, but 1 and 2 never are, so
order.lengthis 1, less than 3, and the result is empty. Returning the partial order would be wrong. - Smallest first, not first found. Example 2,
numCourses = 5with[1, 4],[0, 4],[2, 3], gives[3, 2, 4, 0, 1]. Courses 3 and 4 start ready, and 3 goes first. That makes 2 ready, and 2 beats 4. A plain queue would take 4 before 2. - Reading the pair backwards.
[a, b]meansbcomes first. The arrow goes fromprereq(1)toprereq(0). WithnumCourses = 3and the single pair[0, 2], the answer is[1, 2, 0], with course 2 before course 0.
Testing
numCourses = 4, pairs[[1, 0], [2, 0], [3, 1], [3, 2]]gives[0, 1, 2, 3].numCourses = 5, pairs[[1, 4], [0, 4], [2, 3]]gives[3, 2, 4, 0, 1].numCourses = 3, pairs[[1, 0], [2, 1], [1, 2]]gives an empty buffer.numCourses = 1, no pairs, gives[0].numCourses = 2, pairs[[0, 1], [1, 0]]gives an empty buffer.numCourses = 3, pairs[[0, 2]]gives[1, 2, 0].
