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 function findOrder returns an order in which all the courses can be taken. A course is ready when all its prerequisites have been taken, and whenever several courses are ready, the smallest number goes next. That rule makes the answer unique. If taking all the courses is impossible, the function returns an empty vector.
For numCourses = 4 and prerequisites [[1, 0], [2, 0], [3, 1], [3, 2]], only course 0 is ready at the start. After it, courses 1 and 2 are ready and 1 comes first, then 2, then 3. The answer is [0, 1, 2, 3]. For [[1, 0], [2, 1], [1, 2]] with three courses, courses 1 and 2 wait for each other, so the answer is [].
Approach: take ready courses, smallest first
Think of each pair [a, b] as an arrow from b to a, the course to take first pointing to the course that needs it. A valid order is a topological order of this graph: every course comes after all the courses that point to it. Kahn's algorithm builds one by repeatedly taking a course with no remaining prerequisites.
It keeps an inDegree count for each course, the number of its prerequisites not yet taken. Courses with count 0 are ready. Taking a course removes its arrows: every course that was waiting for it gets its count reduced by 1, and if the count reaches 0, that course becomes ready too.
The plain version keeps the ready courses in a queue. Here the statement asks for the smallest ready course every time, so the ready courses wait in a min-heap. On the second example, numCourses = 5 and [[1, 4], [0, 4], [2, 3]], a plain queue would give [3, 4, 2, 1, 0], which is a valid topological order but not the smallest-first one. With the heap, the result is [3, 2, 4, 0, 1]: after 3 is taken, 2 and 4 are both ready and 2 is smaller.
If the loop ends with fewer than numCourses courses taken, the rest are on a cycle, or wait for a course that is. Their counts never reach 0, so they never enter the heap, and no order exists.
The statement sets O((V + E) log V) time, with V courses and E pairs. Each course is pushed and popped once at O(log V) each, and each pair is looked at once. Searching all the courses for the smallest ready one before every pick would cost O(V * V).
For the first example, the graph lists after the pairs are read are:
graph[0] = [1, 2]
graph[1] = [3]
graph[2] = [3]
graph[3] = []
inDegree = [0, 1, 1, 2]Step by step
- Create
graphas avector<vector<int>>ofnumCoursesempty vectors. Giving the constructor only a size makes that many empty inner vectors.graph[b]will list the courses waiting for courseb. - Create
inDegree, avector<int>ofnumCourseszeros.inDegree[a]counts the prerequisites of courseathat are not taken yet. - Loop over
prerequisiteswithauto& prereq. The&reads each pair in place instead of copying it. - Push
prereq[0]ontograph[prereq[1]]. Courseprereq[1]comes first, and courseprereq[0]waits for it. - Increment
inDegree[prereq[0]]. That course has one more prerequisite. - Create the min-heap
ready, apriority_queue<int, vector<int>, greater<int>>. Apriority_queuekeeps its largest value on top, andgreater<int>flips that, sotop()is the smallest. - Push every course whose
inDegreeis 0 ontoready. A valid order can only start with courses that need nothing. - Create the empty vector
orderfor the courses in the order they are taken. - Loop while the heap is not empty. Each course enters the heap at most once, so the loop runs at most once per course.
- Read
ready.top()intocourseand pop it. This is the key line: of all the ready courses, the smallest number is taken.popreturns nothing, so the top is read first. - Append
coursetoorder. - Loop over
graph[course], the courses waiting for it. For eachnextCourse, decrementinDegree[nextCourse]: one of its prerequisites is now taken. - If the count reaches 0, push
nextCourseontoready. A count reaches 0 only once, so no course enters the heap twice. - After the loop, if
orderis shorter thannumCourses, return{}. Cast the size tointfor the comparison. - Otherwise return
order.
The solution in C++
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> inDegree(numCourses, 0);
for (auto& prereq : prerequisites) {
graph[prereq[1]].push_back(prereq[0]);
inDegree[prereq[0]]++;
}
priority_queue<int, vector<int>, greater<int>> ready;
for (int course = 0; course < numCourses; course++) {
if (inDegree[course] == 0) {
ready.push(course);
}
}
vector<int> order;
while (!ready.empty()) {
int course = ready.top();
ready.pop();
order.push_back(course);
for (int nextCourse : graph[course]) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
ready.push(nextCourse);
}
}
}
if ((int) order.size() < numCourses) {
return {};
}
return order;
}
};
The C++ details worth a closer look:
- The min-heap type.
priority_queue<int, vector<int>, greater<int>>has three template arguments: the element type, the container that stores it, and the comparison. The default comparison,less<int>, makes a max-heap. The container argument has to be given to reach the third. - Heap costs.
pushandpoptakeO(log n)andtoptakesO(1).top()returns a reference to the smallest element, andint course = ready.top()copies it, which is why it is safe to callready.pop()on the next line. (int) order.size().size()is unsigned. Comparing it directly with anintconverts theintto unsigned, which is harmless here but triggers a compiler warning, and it would turn a negative number into a huge one. The cast keeps the comparison between twointvalues.return {};builds an emptyvector<int>from the function's return type.- Range-based loops.
for (int nextCourse : graph[course])copies eachint, which is fine for small values.auto& prereqavoids copying each inner vector.
Complexity
Let V be numCourses and E the number of prerequisite pairs.
Time: O((V + E) log V). Building the graph takes O(V + E). Every course is pushed onto the heap at most once and popped once, each in O(log V), and every pair is looked at once when its first course is taken.
Space: O(V + E). The graph holds one entry per pair, inDegree and order hold V numbers each, and the heap holds at most V courses.
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]. A single course gives[0]. - A cycle of two. With two courses and
[[0, 1], [1, 0]], no course starts with count 0, the heap stays empty, and the function returns[]. - The smallest number is not always first. With
numCourses = 3and[[0, 2], [1, 2]], courses 0 and 1 wait for 2, so the answer is[2, 0, 1]. - Reversing the arrow. In
[a, b],bcomes first. Storing the arrow the other way round would list courses before the ones they need. - Using a plain queue. The order is still valid but not the smallest-first one the statement asks for, as the second example shows.
- A partial cycle. Courses outside a cycle may still be taken, but the function must return
[]when any course cannot be taken, which is what the length check does. In the third example course 0 is taken, but the answer is still empty.
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, no pairs, gives[0].numCourses = 3, no pairs, gives[0, 1, 2].numCourses = 3,[[0, 2], [1, 2]]gives[2, 0, 1].numCourses = 3,[[2, 0], [1, 0]]gives[0, 1, 2].
