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 method FindOrder returns an order in which all the courses can be taken, as a List<int>. A course is ready when all its prerequisites have been taken, and whenever several courses are ready, the one with the smallest number goes next. That rule makes the answer unique. If taking every course is impossible, the method returns an empty list.
In the first example, numCourses = 4 and prerequisites = {{1,0},{2,0},{3,1},{3,2}}. Only course 0 is ready at first. After it, courses 1 and 2 are ready and 1 comes first, then 2, and finally 3. The answer is [0, 1, 2, 3]. In the second example, numCourses = 5 and prerequisites = {{1,4},{0,4},{2,3}}, the answer is [3, 2, 4, 0, 1]: course 3 is smaller than 4, and once it is taken course 2 is ready and smaller than 4. In the third example, courses 1 and 2 need each other, so the answer is [].
The lesson asks for O((V + E) log V) time and O(V + E) extra space, where V is the number of courses and E the number of pairs.
Approach: Kahn's algorithm with a priority queue
Treat each pair as an arrow from the course to take first to the course that needs it. A valid order takes every course after all the arrows pointing into it, which is called a topological order. Kahn's algorithm builds one:
- Count, for every course, how many prerequisites are still untaken. This is its in-degree.
- Take any course whose count is 0. Taking it removes its outgoing arrows: each course waiting for it has its count lowered by one.
- 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 smallest ready course must always be taken first, so they wait in a min-heap instead, which in C# is a PriorityQueue. Each course enters the heap once and leaves it once, at O(log V) each, and each pair is looked at once. Scanning all the courses for the smallest ready one before every pick would cost O(V²).
The heap matters. With a plain queue, the second example comes out as [3, 4, 2, 1, 0]: it is a valid order, but it takes 4 while the smaller course 2 is ready, so it is not the answer.
If fewer than numCourses courses get taken, the rest wait on a cycle, or on a course that does, and their counts never reach 0. In that case no order exists.
Step by step
- Create
graph, aList<List<int>>. Entrygraph[b]will list the courses that wait for courseb. - Loop over the courses and add a new empty
List<int>for each. The inner lists are separate objects, so they are added one at a time. - Create
inDegree, anintarray of sizenumCourses, filled with zeros.inDegree[a]counts the prerequisites of courseanot yet taken. - Loop over
prerequisiteswithforeach. For each pair, addprereq[0]tograph[prereq[1]](the course to take first points at the course that waits) and add one toinDegree[prereq[0]]. - Create the heap, a
PriorityQueue<int, int>namedready. Each element comes with a priority, andDequeueremoves the element with the smallest priority. - Enqueue every course with in-degree 0, using the course number as both element and priority:
ready.Enqueue(course, course). These are the places any valid order can start. - Create
order, an emptyList<int>for the courses in the order they are taken. - Loop while
ready.Countis above 0. Dequeue the smallest ready course and add it toorder. Every course in the heap has all its prerequisites taken, so this is safe. - Visit the courses waiting for it. For each
nextCourseingraph[course], subtract one from its in-degree. If the result is 0, enqueue it: its last prerequisite was just taken. A count reaches 0 only once, so each course enters the heap at most once. - After the loop, return a new empty list if
order.Count < numCourses. Otherwise returnorder.
The solution in C#
class Solution {
public List<int> FindOrder(int numCourses, int[][] prerequisites) {
List<List<int>> graph = new List<List<int>>();
for (int i = 0; i < numCourses; i++) {
graph.Add(new List<int>());
}
int[] inDegree = new int[numCourses];
foreach (int[] prereq in prerequisites) {
graph[prereq[1]].Add(prereq[0]);
inDegree[prereq[0]]++;
}
PriorityQueue<int, int> ready = new PriorityQueue<int, int>();
for (int course = 0; course < numCourses; course++) {
if (inDegree[course] == 0) {
ready.Enqueue(course, course);
}
}
List<int> order = new List<int>();
while (ready.Count > 0) {
int course = ready.Dequeue();
order.Add(course);
foreach (int nextCourse in graph[course]) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
ready.Enqueue(nextCourse, nextCourse);
}
}
}
if (order.Count < numCourses) {
return new List<int>();
}
return order;
}
}
The C# details worth knowing:
PriorityQueue<TElement, TPriority>. It is inSystem.Collections.Generic, available since .NET 6. It is a min-heap:Dequeuereturns the element with the smallest priority, and calling it on an empty queue throws anInvalidOperationException. The loop condition rules that out. It takes two type arguments, even when, as here, the element and the priority are the same number.- A list of lists.
List<List<int>>starts empty, and indexing it withgraph[b]works only after the inner list has been added. That is why the first loop adds one list per course before any pair is read. - Value types in the array.
inDegree[prereq[0]]++changes the array element in place. A newint[]is filled with zeros, so no initialization loop is needed. - Same name, separate scopes. The loop variable
coursein theforloop and theint courseinside thewhilebody don't collide, because the first exists only inside itsfor. - Returning an empty list. A cycle gives
new List<int>(), notnull. A caller can then useCountor aforeachwithout a null check. - The input array is not changed. The method only reads
prerequisites.
Complexity
Time: O((V + E) log V). Building the graph is O(V + E). Each course is enqueued and dequeued once, at O(log V) each. Each pair is looked at once, when its first course is taken. With 100,000 courses chained one after another, the method returns all of them at once.
Space: O(V + E). The graph holds V lists with E entries in total, plus the in-degree array, the heap and the order, each at most V items.
Edge cases and common mistakes
- No prerequisites. With
numCourses = 3and no pairs, the answer is[0, 1, 2]: everything is ready, and the heap gives them smallest first. A single course with no pairs returns[0]. - Reading the pair backwards. In
[a, b], coursebcomes first. For{{0, 1}}with two courses, the answer is[1, 0]. - A cycle.
{{0,1},{1,0}}gives[], because no course starts with in-degree 0 and the heap is empty from the beginning. A cycle in only part of the graph, as in the third example, also gives[], even though course 0 could be taken. - Using a plain queue. The result may be a valid topological order but not the one with the smallest ready course first.
- Returning a partial order. Check
order.Count < numCoursesand return an empty list instead. - Swapping the arrow direction. Adding
prereq[1]tograph[prereq[0]]reverses every dependency, and the order comes out backwards. - Forgetting that counts reach 0 once. Enqueuing a course on any decrement, rather than only when its count reaches 0, would add it several times.
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 = 1, no pairs, gives[0].numCourses = 3, no pairs, gives[0, 1, 2].numCourses = 2,prerequisites = {{0,1}}gives[1, 0].numCourses = 2,prerequisites = {{0,1},{1,0}}gives[].
