Problem overview
There are num_courses courses, numbered from 0. Each pair [a, b] in prerequisites means that course b must be taken before course a. The function find_order returns an order in which all the courses can be taken, as a Vec<i32>. A course is ready when all its prerequisites have been taken. When several courses 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 vector.
For num_courses = 4 and prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] the result is [0, 1, 2, 3]. Only course 0 is ready at first. Once it is taken, courses 1 and 2 are both ready and 1 comes first. Course 3 needs both. For [[1, 0], [2, 1], [1, 2]] with 3 courses the result is empty: courses 1 and 2 wait for each other, a cycle, so neither can ever be taken.
Approach: Kahn's algorithm with a min-heap
The prerequisites form a directed graph: each pair [a, b] is an arrow from b to a, from the course to take first to the course that needs it. An order that respects all the arrows is a topological order, and Kahn's algorithm builds one.
For every course, count its prerequisites that haven't been taken yet, called its in-degree. A course with count 0 is ready. Take a ready course, add it to the order, and for each course that waits for it, lower that course's count by one. A count that reaches 0 means a new course is ready.
The usual version keeps the ready courses in a queue. Here the rule is to take the smallest ready course, so they wait in a min-heap instead. Each course enters and leaves the heap once, at O(log V) each. Scanning all the courses for the smallest ready one before every pick would cost O(V²).
If the order ends up with fewer courses than num_courses, the missing ones are on a cycle or wait for a course that is. Their counts never reach 0, and no order exists.
Here is the run for num_courses = 5 and prerequisites = [[1, 4], [0, 4], [2, 3]]. The initial graph is [[], [], [], [2], [1, 0]] and in_degree is [1, 1, 1, 0, 0]. Courses 3 and 4 start in the heap.
took 3 ready now [2, 4]
took 2 ready now [4]
took 4 ready now [0, 1]
took 0 ready now [1]
took 1 ready now []
The order is [3, 2, 4, 0, 1]. Course 3 comes before 4 because it is smaller. Taking 3 readies course 2, which is smaller than 4, so 2 comes next.
Step by step
- Build the graph as a mutable
Vec<Vec<usize>>with one empty vector per course.graph[b]will list the courses that wait for courseb. Courses are stored asusize, so they can index the vectors directly. - Create
in_degreeas a mutable vector of zeros, one per course.in_degree[a]will count the prerequisites of courseanot taken yet. - Loop over
&prerequisites, borrowing the vector. Each pair becomes one arrow. - Push
prereq[0] as usizeontograph[prereq[1] as usize]: courseprereq[1]comes first, and courseprereq[0]waits for it. The pairs holdi32, soas usizemakes them indexes. - Add 1 to
in_degree[prereq[0] as usize]. That course has one more prerequisite. Rust has no++operator. - Create
ready, a mutableBinaryHeap<Reverse<usize>>. Rust's heap gives back its largest value first, and wrapping each course inReverseflips the comparison so the smallest comes out first. - Loop over every course from 0 to
num_courses. - Push
Reverse(course)when itsin_degreeis 0. The courses that need nothing are where an order can start. - Create
order, a mutableVec<i32>, for the courses in the order they are taken. - Loop while the heap is not empty. Each course enters the heap at most once, so this runs at most once per course.
- Pop the smallest ready course with
ready.pop().unwrap().0. This is the key line: taking the smallest ready course is what makes the order unique. - Push
course as i32ontoorder. - Loop over the courses that wait for it,
&next_courseover&graph[course]. - Subtract 1 from
in_degree[next_course]: one of its prerequisites has been taken. - Push
Reverse(next_course)when its count is 0. Its last prerequisite was just taken. A count reaches 0 only once, so each course enters the heap once. - If
order.len() < num_courses as usize, returnVec::new(). Some courses never became ready. - Return
orderas the last expression.
The solution in Rust
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
let mut graph: Vec<Vec<usize>> = vec![Vec::new(); num_courses as usize];
let mut in_degree = vec![0; num_courses as usize];
for prereq in &prerequisites {
graph[prereq[1] as usize].push(prereq[0] as usize);
in_degree[prereq[0] as usize] += 1;
}
let mut ready: BinaryHeap<Reverse<usize>> = BinaryHeap::new();
for course in 0..num_courses as usize {
if in_degree[course] == 0 {
ready.push(Reverse(course));
}
}
let mut order: Vec<i32> = Vec::new();
while !ready.is_empty() {
let course = ready.pop().unwrap().0;
order.push(course as i32);
for &next_course in &graph[course] {
in_degree[next_course] -= 1;
if in_degree[next_course] == 0 {
ready.push(Reverse(next_course));
}
}
}
if order.len() < num_courses as usize {
return Vec::new();
}
order
}
}
The Rust details worth a closer look:
Reverseand the heap.BinaryHeapis a max-heap.std::cmp::Reverseis a one-field wrapper whose ordering is the opposite of the value inside it, soBinaryHeap<Reverse<usize>>pops the smallest course first. The popped value is aReverse, so.0takes the course out of it. The twouselines at the top of the lesson's file bring both names into scope.vec![Vec::new(); n]. The macro clones the value for every slot, so each course gets its own empty vector. That requires the element to implementClone, whichVec<usize>does.- Inferred types. The type of
in_degreeis not written. The literal0and the comparisons make itVec<i32>. The type ofgraphis spelled out becauseVec::new()alone doesn't say what the inner vectors hold. - Borrowing in the inner loop.
for &next_course in &graph[course]borrowsgraphimmutably while the body changesin_degreeandready. Those are separate variables, so the borrow checker accepts it. pop().unwrap().popreturns anOption. The loop condition checks the heap is not empty, so theunwrapcan't fail.- Returning an empty vector.
Vec::new()allocates nothing, and the last expressionorderhas no semicolon, so it is the returned value.
Complexity
Time: O((V + E) log V), where V is the number of courses and E the number of pairs. Building the graph looks at each pair once. Each course is pushed to and popped from the heap at most once, at O(log V) each, and the inner loop looks at each pair once over the whole run.
Space: O(V + E). The graph holds one entry per pair, and in_degree, ready and order each hold at most one entry per course.
Edge cases and common mistakes
- No prerequisites. With 3 courses and an empty list, every course starts ready and the result is
[0, 1, 2]. With one course the result is[0]. - A cycle. For the third example, only course 0 is taken,
orderhas length 1 instead of 3, and the function returns an empty vector. A cycle in part of the graph makes the whole answer empty, even though some courses could be taken. - Using a plain queue. A queue also gives a valid topological order, but not the smallest-first one. For the first example both give
[0, 1, 2, 3], but with[[1, 4], [0, 4], [2, 3]]a queue that starts from[3, 4]would take 3, then 4, then 2, which is not what the rule asks for. - Forgetting
Reverse. Without it, the heap would pop the largest ready course first, and the order would break the smallest-first rule. - Swapping the pair. The pair
[a, b]meansbcomes first. Reversing the roles gives a different order: with 2 courses and[[0, 1]]the result is[1, 0], not[0, 1]. - Comparing the length with the wrong type.
order.len()is ausize, sonum_coursesis converted withas usizefor the comparison.
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 prerequisites, gives
[0, 1, 2]. - 1 course, no prerequisites, gives
[0]. - 2 courses,
[[0, 1]]gives[1, 0].
