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. findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] returns an order in which all the courses can be taken, or an empty array if there is none.
Many orders can be valid, so the lesson adds a rule that makes the answer unique: a course is ready when all its prerequisites are taken, and whenever several courses are ready, the one with the smallest number comes next.
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 1 is ready, so it is not accepted. For numCourses = 3 and [[1, 0], [2, 1], [1, 2]] courses 1 and 2 wait for each other, so the answer is [].
Approach: Kahn's algorithm with the ready courses in a min-heap
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. A course can be taken when no arrow points into it that hasn't been used up. Kahn's algorithm works like this:
- For each course, count the arrows pointing into it, its in-degree: the number of prerequisites not taken yet.
- Collect the courses with in-degree 0. They are ready.
- Take a ready course. For each course that waits for it, lower its in-degree by 1, and if that reaches 0, the course is now ready.
- Repeat until nothing is ready.
If every course was taken, the order is valid. If some were not, they wait on a cycle, or on a course that does, and no order exists.
Which ready course to take is where the lesson's rule comes in. A plain queue hands them out in the order they became ready, which isn't the order of their numbers. With numCourses = 5 and prerequisites = [[1, 4], [0, 4], [2, 3]] a queue gives [3, 4, 2, 1, 0]: course 4 makes 1 and 0 ready in that order, and the queue keeps it. The expected answer is [3, 2, 4, 0, 1]. A min-heap always returns the smallest value it holds, so the next course taken is always the smallest ready one. The lesson provides a MinHeap: insert(_:) adds a value, extract() removes and returns the smallest, and the heap also has peek(), count and isEmpty.
Scanning all the courses for the smallest ready one before each pick would cost O(V²). With a heap, each course enters and leaves once, at O(log V) per operation.
Here is the run for the second example. After each course is taken, the output shows the order so far and the in-degrees:
graph [[], [], [], [2], [1, 0]] inDegree [1, 1, 1, 0, 0]
took 3 order [3] inDegree [1, 1, 0, 0, 0]
took 2 order [3, 2] inDegree [1, 1, 0, 0, 0]
took 4 order [3, 2, 4] inDegree [0, 0, 0, 0, 0]
took 0 order [3, 2, 4, 0] inDegree [0, 0, 0, 0, 0]
took 1 order [3, 2, 4, 0, 1] inDegree [0, 0, 0, 0, 0]
The first line is the state before anything is taken. The graph entry at index 3 is [2]: course 2 waits for course 3.
Step by step
- Create
graphasnumCoursesempty arrays.graph[b]will hold the courses that wait for courseb. - Create
inDegreewithnumCourseszeros.inDegree[a]counts the prerequisites of courseathat are not taken yet. - Loop over
prerequisiteswith the variableprereq. Each pair becomes one arrow. - Append
prereq[0]tograph[prereq[1]]. Courseprereq[1]comes first, and courseprereq[0]waits for it. - Add 1 to
inDegree[prereq[0]]: that course has one more prerequisite. - Create
ready, aMinHeap()for the courses that can be taken now. It is avar, because inserting and extracting change it. - Loop over every course from 0 up to
numCourses - 1. - Insert each course with
inDegree[course] == 0intoready. These need nothing, so any valid order can start with them. - Create
order, an empty[Int]for the courses in the order they are taken. - Loop while the heap isn't empty. Each course enters the heap at most once, so this runs at most once per course.
- Extract the smallest ready course into
course. This is the key line. Every course in the heap has all its prerequisites taken, so taking it now is safe. - Append
coursetoorder. - Loop over
graph[course], the courses waiting for it, with the variablenextCourse. - Subtract 1 from
inDegree[nextCourse]: one of its prerequisites is now taken. - If that count is 0, insert
nextCourseintoready. A count reaches 0 only once, so no course is inserted twice. - If
order.count < numCourses, return[]. Courses on a cycle never reach in-degree 0, and neither do the courses that need them. - Otherwise return
order.
The solution in Swift
class Solution {
func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
var graph = [[Int]](repeating: [], count: numCourses)
var inDegree = [Int](repeating: 0, count: numCourses)
for prereq in prerequisites {
graph[prereq[1]].append(prereq[0])
inDegree[prereq[0]] += 1
}
var ready = MinHeap()
for course in 0..<numCourses {
if inDegree[course] == 0 {
ready.insert(course)
}
}
var order = [Int]()
while !ready.isEmpty {
let course = ready.extract()
order.append(course)
for nextCourse in graph[course] {
inDegree[nextCourse] -= 1
if inDegree[nextCourse] == 0 {
ready.insert(nextCourse)
}
}
}
if order.count < numCourses {
return []
}
return order
}
}
The Swift details worth a closer look:
[[Int]](repeating: [], count: numCourses). This makesnumCoursesempty arrays. Arrays are value types, so the entries are independent copies, and appending tograph[b]doesn't touch any other entry.- Appending through a subscript.
graph[prereq[1]].append(prereq[0])changes the inner array in place. It works becausegraphis avar. MinHeapis provided. The lesson supplies it, so the solution doesn't define it. It has to be stored in avar, sinceinsertandextractchange it.extract()returns the value itself, not an optional, so the result goes straight intoorder.append. That is safe because the loop only runs while!ready.isEmpty.- No
++. Swift has no increment operator, so counts change with+= 1and-= 1. - Empty array literal.
return []works because the return type is[Int], which tells the compiler what the literal is.[Int]()is another way to write an empty array when no type is known from context.
Complexity
Time: O((V + E) log V), where V is numCourses and E the number of pairs. Building the graph takes O(V + E). Each course is inserted into the heap and extracted once, at O(log V) each. Each pair is looked at once, when its first course is taken.
Space: O(V + E). The adjacency lists hold one entry per pair, and inDegree, the heap and order hold at most one entry per course.
Edge cases and common mistakes
- No prerequisites. With an empty list, every course is ready at once, and the answer is all the courses in increasing order:
findOrder(3, [])returns[0, 1, 2]. - One course.
findOrder(1, [])returns[0]. - The direction of a pair.
[a, b]meansbcomes first.findOrder(2, [[0, 1]])returns[1, 0], whilefindOrder(2, [[1, 0]])returns[0, 1]. Swapping the two indices gives the reverse order. - A cycle.
findOrder(2, [[0, 1], [1, 0]])returns[], since neither course ever becomes ready. A cycle that doesn't include every course still gives an empty array:findOrder(4, [[1, 0], [2, 1], [1, 2]])returns[], although courses 0 and 3 could be taken. - Using a queue. A first-in, first-out queue gives a valid order, but not always the smallest-first one, as the
[3, 4, 2, 1, 0]result above shows. - Returning a partial order. If the loop ends with fewer than
numCoursescourses taken, the answer is[], not what was collected so far.
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]]gives[1, 0].numCourses = 3,prerequisites = [[0, 2], [1, 2]]gives[2, 0, 1].
