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 function findOrder returns an order in which all courses can be taken. A course is ready once all its prerequisites are taken, and whenever several courses are ready, the smallest number goes next. That rule makes the answer unique. If taking every course is impossible, the function returns an empty slice.
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 the start. After it, courses 1 and 2 are both ready and 1 is smaller. Course 3 needs both 1 and 2. The order 0, 2, 1, 3 respects the prerequisites too, but it takes 2 while the smaller 1 is ready, so it isn't the answer.
For numCourses = 3 and [[1, 0], [2, 1], [1, 2]], courses 1 and 2 wait for each other. This is a cycle, so the answer is the empty slice.
Approach: Kahn's algorithm, with a heap for the ready courses
Treat each pair [a, b] as an arrow from b to a, from the course to take first to the course that needs it. Two structures describe the graph. graph[b] lists the courses waiting for b. inDegree[a] counts the prerequisites of a that haven't been taken yet. For the first example, that gives graph = [[1 2] [3] [3] []] and inDegree = [0 1 1 2].
Kahn's algorithm works like this: take any course whose count is 0, then walk its list and lower the count of every course that was waiting for it. A course that reaches 0 is ready. Repeat until nothing is ready. If every course was taken, the order is valid. If some were not, they sit on a cycle, or wait for a course that does.
The one change for this lesson is how the ready courses wait. A plain queue takes them in the order they became ready, which isn't the same as smallest first. For the second example, numCourses = 5 and [[1, 4], [0, 4], [2, 3]], a queue gives [3 4 2 1 0], but the required answer is [3 2 4 0 1]: after taking 3, the ready courses are 2 and 4, and 2 must go first. A min-heap always hands back the smallest ready course. Each course enters and leaves the heap once, at O(log V) each. Scanning all courses for the smallest ready one before every pick would cost O(V²).
Step by step
- Create
graphasmake([][]int, numCourses). Every entry starts as anilslice, andappendworks on anilslice, so no further setup is needed. - Create
inDegreeasmake([]int, numCourses), filled with zeros. A course can be taken when its count is 0. - Loop over
prerequisiteswithrange, ignoring the index with_. Each pair becomes one arrow. - Append
prereq[0]tograph[prereq[1]]and store the result back: the courseprereq[1]comes first, andprereq[0]waits for it. - Add 1 to
inDegree[prereq[0]]. That course now has one more prerequisite. - Create
readyas&minHeap{}. The lesson providesminHeapabove the function.heap.Pushandheap.Popfromcontainer/heapneed a pointer to it, which&gives. - Loop over every course from 0 to
numCourses - 1. The courses that need nothing are where an order can start. - Push the course with
heap.Push(ready, course)when itsinDegreeis 0. - Create
orderas[]int{}. It collects the courses in the order they are taken, and its length counts how many were taken. - Loop while
ready.Len() > 0. Each course enters the heap at most once, so this runs at most once per course. - Take the smallest ready course with
heap.Pop(ready).(int). This is the key line. Every course in the heap has all its prerequisites taken, so it is safe to take. - Append it to
order, storing the result back. - Loop over
graph[course], the courses that were waiting for it. - Subtract 1 from
inDegree[nextCourse]. One of its prerequisites is now taken. - Push
nextCourseif its count reached 0. A count reaches 0 only once, so no course enters the heap twice. - Return an empty slice if
len(order) < numCourses. Courses on a cycle never reach 0, and neither do the courses that need them. - Otherwise return
order.
The solution in Go
func findOrder(numCourses int, prerequisites [][]int) []int {
graph := make([][]int, numCourses)
inDegree := make([]int, numCourses)
for _, prereq := range prerequisites {
graph[prereq[1]] = append(graph[prereq[1]], prereq[0])
inDegree[prereq[0]]++
}
ready := &minHeap{}
for course := 0; course < numCourses; course++ {
if inDegree[course] == 0 {
heap.Push(ready, course)
}
}
order := []int{}
for ready.Len() > 0 {
course := heap.Pop(ready).(int)
order = append(order, course)
for _, nextCourse := range graph[course] {
inDegree[nextCourse]--
if inDegree[nextCourse] == 0 {
heap.Push(ready, nextCourse)
}
}
}
if len(order) < numCourses {
return []int{}
}
return order
}
The Go details worth a closer look:
container/heap. Go's standard heap isn't a ready-made type. It is a set of functions,heap.Pushandheap.Pop, that keep any value implementingheap.Interfacein heap order. The lesson providesminHeap, a min-heap of ints, soheap.Popreturns the smallest value.- Why a pointer.
heap.Pushandheap.Popchange the heap's slice, which is whyreadyis a pointer, made by&minHeap{}. TheLenmethod works through the pointer too. - Type assertion.
heap.Popreturns anany. Writing.(int)gets theintback out. Without it, the value couldn't be used as an index or appended toorder. makeversus[]int{}.make([][]int, numCourses)creates the outer slice withnilentries.order := []int{}creates an empty, non-nilslice, and the failure case returns[]int{}so the answer always is an empty slice, nevernil.- Each pair is a two-element slice.
prereq[0]is the course that waits,prereq[1]the course it needs. The statement's order[a, b]is easy to read backwards.
Complexity
Time: O((V + E) log V). Building the graph takes O(V + E). Each course is pushed and popped once, O(log V) each, and each pair is looked at once when its first course is taken.
Space: O(V + E). graph holds one entry per pair, and inDegree, order and the heap each hold at most V numbers.
Edge cases and common mistakes
- No prerequisites. With
numCourses = 3and an empty list, every course is ready at the start, and the answer is[0 1 2]. - A single course.
numCourses = 1returns[0]. - A cycle.
numCourses = 2with[[0, 1], [1, 0]]has no course ready at the start, soorderstays empty and the function returns[]. In the lesson's third example course 0 is taken, but the order is shorter than 3, so the answer is still empty. A partial order is never returned. - Reversed arrows. Adding
prereq[1]tograph[prereq[0]]flips every dependency. FornumCourses = 3and[[0, 1], [1, 2]], the correct answer is[2 1 0]: course 2 first, because 1 needs it. - Using a queue instead of the heap. It produces a valid order, but not the smallest-first one: on the second example it gives
[3 4 2 1 0]instead of[3 2 4 0 1]. - Returning
orderwithout the length check. A cycle would then give back a partial order that looks like an answer.
Testing
numCourses = 4,[[1,0],[2,0],[3,1],[3,2]]gives[0 1 2 3].numCourses = 5,[[1,4],[0,4],[2,3]]gives[3 2 4 0 1].numCourses = 3,[[1,0],[2,1],[1,2]]gives[].numCourses = 1,[]gives[0].numCourses = 3,[]gives[0 1 2].numCourses = 2,[[0,1]]gives[1 0].numCourses = 2,[[0,1],[1,0]]gives[].numCourses = 3,[[0,1],[1,2]]gives[2 1 0].
