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(int numCourses, int[][] prerequisites) returns an order in which all courses can be taken, as a List<Integer>. Whenever several courses are ready, meaning all their prerequisites are taken, the smallest number goes next, which makes the order unique. If it is impossible to take every course, the method returns an empty list.
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 both ready and 1 is smaller. Course 3 comes last, once 1 and 2 are taken. The order 0, 2, 1, 3 also respects the prerequisites, but it takes 2 while the smaller course 1 is ready, so it isn't the answer.
With [[1,0],[2,1],[1,2]] courses 1 and 2 wait for each other, a cycle, so the answer is [].
Approach: take ready courses from a min-heap
Think of each pair as an arrow from the course to take first 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. For every course, count its in-degree, the number of prerequisites not taken yet. A course with an in-degree of 0 is ready. Take a ready course, then walk through the courses that wait for it and lower each one's count by 1. Any course that reaches 0 has just become ready.
The plain algorithm keeps the ready courses in a queue. Here the smallest ready course must always be next, so they wait in a min-heap, a PriorityQueue in Java. Each course enters and leaves the heap once, at O(log V) each. Scanning all courses for the smallest ready one before each pick would cost O(V²) instead.
If fewer than numCourses courses get taken, the rest are stuck: they are on a cycle, or wait on a course that is. Their counts never reach 0, so no order exists.
A trace
For numCourses = 5 and prerequisites = [[1,4],[0,4],[2,3]] the graph lists are [[], [], [], [2], [1, 0]], so course 3 is followed by 2, and course 4 by 1 and 0. The in-degrees are [1, 1, 1, 0, 0]. Running the loop, the ready courses and the pick at each turn are:
ready=[3, 4]
take 3
ready=[2, 4]
take 2
ready=[4]
take 4
ready=[0, 1]
take 0
ready=[1]
take 1
The order is [3, 2, 4, 0, 1]. Taking 3 made 2 ready, and 2 beat 4 because it is smaller. Taking 4 made 0 and 1 ready, and the smaller one came first.
Step by step
- Build the graph. Create
graphas aList<List<Integer>>, anArrayList.graph.get(b)will hold the courses that wait for courseb. - Add one empty
ArrayListper course. A loop from 0 tonumCourses - 1adds them one at a time. - Create
inDegreeas anintarray of sizenumCourses. It starts with zeros, andinDegree[a]will count the prerequisites ofanot taken yet. - Read each pair. Loop over
prerequisiteswith a variableprereq. For every pair, addprereq[0]tograph.get(prereq[1]), because courseprereq[1]comes first. Then doinDegree[prereq[0]]++. - Create the heap.
readyis aPriorityQueue<Integer>.addputs a value in andpollremoves and returns the smallest, each inO(log n). - Seed the heap with every course whose
inDegreeis 0. These are where a valid order can start. If none exists, every course waits for another, and none can be taken. - Create
orderas a newArrayList. It holds 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.
- Take the smallest ready course with
poll()and append it toorder. This is the key line: all its prerequisites are taken, so taking it is safe. - Update its dependants. For each
nextCourseingraph.get(course), subtract 1 frominDegree[nextCourse]. If it reaches 0, addnextCoursetoready. A count reaches 0 only once, so no course enters the heap twice. - Check for a cycle. If
order.size() < numCourses, return a new emptyArrayList. Otherwise returnorder.
The solution in Java
class Solution {
public List<Integer> findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] inDegree = new int[numCourses];
for (int[] prereq : prerequisites) {
graph.get(prereq[1]).add(prereq[0]);
inDegree[prereq[0]]++;
}
PriorityQueue<Integer> ready = new PriorityQueue<>();
for (int course = 0; course < numCourses; course++) {
if (inDegree[course] == 0) {
ready.add(course);
}
}
List<Integer> order = new ArrayList<>();
while (!ready.isEmpty()) {
int course = ready.poll();
order.add(course);
for (int nextCourse : graph.get(course)) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
ready.add(nextCourse);
}
}
}
if (order.size() < numCourses) {
return new ArrayList<>();
}
return order;
}
}
The Java details worth a closer look:
- A list of lists.
new ArrayList<>()creates one list, so the inner lists must be added one by one in a loop. The diamond<>lets the compiler fill in the type arguments. - Unboxing.
int course = ready.poll();converts anIntegerfrom the heap to anint, andfor (int nextCourse : graph.get(course))unboxes each list entry.ready.add(course)boxes the value again. PriorityQueueorders by natural order. ForIntegerthat is ascending, sopoll()returns the smallest value. Its iteration order and its printed form are not sorted, so onlypoll()gives values in order.- Return type. The method returns
List<Integer>, so returning anArrayListis fine. An empty list is a valid result, notnull. graph.get(...).add(...). The first call fetches the inner list for a course, andaddchanges that list in place.
Complexity
Let V be numCourses and E the number of pairs.
Time: O((V + E) log V). Building the graph is O(V + E). Each course is added to and polled from the heap once, at O(log V) each. Each pair is looked at once, when its first course is taken.
Space: O(V + E). The graph holds V lists and E entries. inDegree, the heap and order each hold at most V numbers.
Edge cases and common mistakes
- No prerequisites.
findOrder(3, new int[][]{})returns[0, 1, 2]: all courses are ready at once and the heap hands them out smallest first. With one course, the result is[0]. - Cycles.
[[0,1],[1,0]]with 2 courses returns[]. A cycle somewhere else in the graph also gives[], even though other courses could be taken, as in the third example where course 0 is free. - Direction of the pair.
[a, b]meansbfirst. WithfindOrder(2, new int[][]{{0, 1}})the answer is[1, 0]. Reversing the arrow gives[0, 1], which is wrong. - A chain that is not in number order. With
[[3,0],[0,1],[1,2]]and 4 courses, the answer is[2, 1, 0, 3]. Smallest-first applies only among courses that are ready. - Using a queue instead of a heap. A plain
ArrayDequegives a valid order but not always the smallest-first one that this problem asks for. - Adding a course twice. Adding a course to the heap whenever its count drops, instead of only when it reaches 0, would put it in more than once.
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 = 3,[]gives[0, 1, 2].numCourses = 2,[[0,1]]gives[1, 0].numCourses = 4,[[3,0],[0,1],[1,2]]gives[2, 1, 0, 3].
