Problem overview
There are numCourses courses numbered 0 to numCourses - 1. Each pair [a, b] in prerequisites means course b must be taken before course a. findOrder returns an order that takes all the courses, as a List<Int>. A course is ready when all its prerequisites are taken, and whenever several are ready the one with the smallest number goes next, which makes the order unique. If no order can take every course, the function returns an empty list.
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 ready and 1 is smaller. Course 3 comes last. 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.
For [[1, 0], [2, 1], [1, 2]] with 3 courses, courses 1 and 2 wait for each other. That is a cycle, so the answer is [].
Approach
View each pair as an arrow from the course to take first to the course that needs it. Then you want an order in which every arrow points forward: a topological order. Kahn's algorithm builds one:
- Count, for each course, how many prerequisites it still waits for: its in-degree.
- Courses with count 0 are ready. Take one.
- Taking a course removes its arrows: each course that waited for it gets its count lowered by 1. A course whose count reaches 0 is now ready.
- Repeat until nothing is ready.
The usual version keeps the ready courses in a plain queue. Here the rule says the smallest ready course goes first, so they wait in a min-heap instead. With a plain queue, the pairs [[1, 4], [0, 4], [2, 3]] with 5 courses would give [3, 4, 2, 1, 0], because course 1 was added to the queue before 0. The heap gives [3, 2, 4, 0, 1]: after 3, courses 2 and 4 are ready and 2 is smaller, and after 4 the courses 0 and 1 are ready, smaller first.
If fewer than numCourses courses get taken, the rest wait on a cycle, or on a course that is on one, and no order exists. Searching all courses for the smallest ready one before every pick would cost O(V²). The heap makes each pick O(log V), so the total is O((V + E) log V) for V courses and E pairs.
Step by step
- The graph.
Array(numCourses) { mutableListOf<Int>() }gives every course its own empty list, because the lambda runs once per course.graph[b]holds the courses that wait for courseb. - The counts.
IntArray(numCourses)starts as zeros.inDegree[a]counts the prerequisites of courseathat are not taken yet. - Read the pairs. For each
prereq, addprereq[0]tograph[prereq[1]](courseprereq[1]comes first), and doinDegree[prereq[0]]++. - The heap.
PriorityQueue<Int>()is a min-heap:addputs a value in andpoll()removes and returns the smallest, each in O(log n). - Seed it. Loop over
0 until numCoursesand add every course withinDegree[course] == 0. If none is free, every course waits for another and none can be taken. - The result list.
orderis an emptymutableListOf<Int>(). Its size also counts the courses taken so far. - The main loop. While
ready.isNotEmpty(), take the smallest course withpoll(), append it toorder, and visitgraph[course]. This is the key line: of all the ready courses, the smallest number comes next. - Release the waiting courses. For each
nextCourse, doinDegree[nextCourse]--. When it reaches 0, add it toready. A count reaches 0 only once, so each course enters the heap at most once. - Check for a cycle. If
order.size < numCourses, returnlistOf(). Otherwise returnorder.
The solution in Kotlin
class Solution {
fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): List<Int> {
val graph = Array(numCourses) { mutableListOf<Int>() }
val inDegree = IntArray(numCourses)
for (prereq in prerequisites) {
graph[prereq[1]].add(prereq[0])
inDegree[prereq[0]]++
}
val ready = PriorityQueue<Int>()
for (course in 0 until numCourses) {
if (inDegree[course] == 0) {
ready.add(course)
}
}
val order = mutableListOf<Int>()
while (ready.isNotEmpty()) {
val course = ready.poll()
order.add(course)
for (nextCourse in graph[course]) {
inDegree[nextCourse]--
if (inDegree[nextCourse] == 0) {
ready.add(nextCourse)
}
}
}
if (order.size < numCourses) {
return listOf()
}
return order
}
}
Kotlin details worth knowing:
PriorityQueuecomes from Java. It isjava.util.PriorityQueue, which Kotlin on the JVM can use directly. In a file of your own, addimport java.util.PriorityQueueat the top.- One list per course. The lambda creates a separate list per course. Filling the array with one shared list would mix all the courses' neighbours.
inDegree[x]++works on array elements and changes the element in place.- The empty result.
listOf()infersList<Int>from the return type. The function returns a read-onlyList<Int>, whileorderis aMutableList<Int>that is returned as aList. poll()returns null on an empty queue. It is safe here because the loop condition checksisNotEmpty()first.
Complexity
Time: each course is pushed to the heap and popped once, O(log V) each, and each pair is looked at once when its first course is taken: O((V + E) log V).
Space: the graph holds E entries, plus the arrays and the heap with V entries: O(V + E).
Edge cases and common mistakes
- No prerequisites. With
numCourses = 3and no pairs, every course is ready and the answer is[0, 1, 2]. With one course the answer is[0]. - A cycle.
[[0, 1], [1, 0]]with 2 courses leaves nothing ready at the start, soorderstays empty and the function returns[]. - A cycle behind other courses. Courses outside the cycle are still taken, but the final size check catches the missing ones. In the third example, course 0 is taken and the answer is still
[]. - Arrow direction. The pair
[a, b]meansbfirst. Usinggraph[a].add(b)reverses all the arrows. With[[0, 1]]the correct answer is[1, 0]. - A plain queue. It gives a valid topological order, but not the smallest-first order the task asks for.
- Returning the partial order. On a cycle the function returns an empty list, not the courses taken so far.
Testing
4 courses, [[1,0],[2,0],[3,1],[3,2]] gives [0, 1, 2, 3]
5 courses, [[1,4],[0,4],[2,3]] gives [3, 2, 4, 0, 1]
3 courses, [[1,0],[2,1],[1,2]] gives []
3 courses, no pairs gives [0, 1, 2]
2 courses, [[0,1]] gives [1, 0]
2 courses, [[0,1],[1,0]] gives []
