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, prerequisites) 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 one with the smallest number goes next. That rule makes the answer unique. If no order can take every course, the function returns an empty list.
With 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. Taking it makes 1 and 2 ready, and 1 is smaller. Course 3 comes last. With [[1, 0], [2, 1], [1, 2]] and 3 courses, courses 1 and 2 wait for each other, a cycle, so the answer is [].
Approach: Kahn's algorithm, with a heap instead of a queue
Draw each pair [a, b] as an arrow from b to a, from the course to take first to the course that needs it. Taking a valid order of all the courses is a topological sort of this graph. Kahn's algorithm builds one by repeatedly taking a course with no remaining prerequisites and removing its arrows.
To know when a course is ready, keep inDegree[a], the number of prerequisites of a not yet taken. A course with count 0 is ready. Taking a course lowers the count of every course waiting for it, and any count that reaches 0 puts that course among the ready ones.
The usual version keeps the ready courses in a queue. Here the order is fixed by the rule "smallest ready course first", so the ready courses wait in a min-heap, which always returns the smallest number. Each course enters and leaves the heap once, at O(log V) each, and each pair is looked at once, so the total is O((V + E) log V), where V is numCourses and E is the number of pairs. Searching all the courses for the smallest ready one before each pick would cost O(V²).
If fewer than numCourses courses end up taken, the rest wait on a cycle, or on a course that does, and no order exists.
For numCourses = 5 and prerequisites = [[1, 4], [0, 4], [2, 3]], the graph is [[], [], [], [2], [1, 0]] (the list at index b holds the courses waiting for b) and the in-degrees are [1, 1, 1, 0, 0]. The run goes:
heap [3, 4] take 3
heap [2, 4] take 2
heap [4] take 4
heap [0, 1] take 0
heap [1] take 1
The order is [3, 2, 4, 0, 1].
Step by step
- Build
graphas[[] for _ in range(numCourses)].graph[b]will hold the courses that wait for courseb. A list comprehension makes separate lists, while[[]] * numCourseswould repeat one list object. - Create
inDegree = [0] * numCourses.inDegree[a]counts the prerequisites of courseanot yet taken. The name comes from graphs: the in-degree of a vertex is the number of arrows pointing into it. - Loop over
prerequisiteswithprereq. Each pair becomes one arrow. - Append
prereq[0]tograph[prereq[1]]. Courseprereq[1]comes first, andprereq[0]waits for it. The arrow points forward in time: when a course is taken, its list names the courses that get one prerequisite closer. - Add 1 to
inDegree[prereq[0]]. That course has one more prerequisite. After the loop,inDegree[a]is the number of input pairs[a, b]. - Create an empty list
ready. It will be the min-heap of courses that can be taken now. - Loop
courseoverrange(numCourses). The courses that need nothing are where any valid order can start. - If
inDegree[course] == 0, callheapq.heappush(ready, course). If no course is free at the start, every course waits for another, and none can be taken. - Create an empty list
order. It holds the courses in the order they are taken. - Loop
while ready. Each course enters the heap at most once, so this runs at most once per course. - Pop the smallest ready course with
heapq.heappop(ready). This is the key line. Of all the ready courses, the smallest number comes next, which makes the order unique. Every course in the heap has all its prerequisites taken, so taking it now is safe. - Append the course to
order. Each course lands after all its prerequisites. - Loop
nextCourseovergraph[course]. Over the whole run, each pair is looked at once. - Subtract 1 from
inDegree[nextCourse]. One of its prerequisites is now taken, and its arrow is gone. - If the count is now 0, push
nextCourseontoready. Its last prerequisite was just taken. A count reaches 0 only once, so each course enters the heap at most once. - If
len(order) < numCourses, return[]. Courses on a cycle wait for each other, so their counts never reach 0 and they never enter the heap, nor does any course that needs one of them. - Otherwise return
order.
The solution in Python
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = [[] for _ in range(numCourses)]
inDegree = [0] * numCourses
for prereq in prerequisites:
graph[prereq[1]].append(prereq[0])
inDegree[prereq[0]] += 1
ready = []
for course in range(numCourses):
if inDegree[course] == 0:
heapq.heappush(ready, course)
order = []
while ready:
course = heapq.heappop(ready)
order.append(course)
for nextCourse in graph[course]:
inDegree[nextCourse] -= 1
if inDegree[nextCourse] == 0:
heapq.heappush(ready, nextCourse)
if len(order) < numCourses:
return []
return order
Python details:
heapqworks on a plain list. It is a module of the standard library (in a file of your own, addimport heapq).heappushadds a value andheappopremoves and returns the smallest, each in O(log n). The list itself is only partly sorted: only its first element,ready[0], is guaranteed to be the smallest. Don't read the list as if it were sorted, and always take values out withheappop.- It is a min-heap. Python's
heapqpops the smallest value first, which is exactly the rule here. A max-heap would need negated values. - Separate lists.
[[] for _ in range(numCourses)]evaluates[]once per course. Writing[[]] * 3and appending 1 to the first list gives[[1], [1], [1]], because all three are the same list. - The empty list is a valid answer. Returning
[]means "no order exists", not "no courses".
Complexity
Building the graph takes O(V + E). Each course is pushed onto the heap and popped at most once, O(log V) each, and each pair is looked at once when its first course is taken. In total that is O((V + E) log V) time. The graph, the in-degree list, the heap and the answer together take O(V + E) space.
Edge cases and common mistakes
- No prerequisites. Every course is ready at once, and the heap hands them out in increasing order: with 3 courses the answer is
[0, 1, 2]. With a single course and no pairs it is[0]. - Cycles. A cycle keeps its courses out of the heap forever, so
len(order)stays belownumCoursesand the function returns[]. Two courses that need each other,[[0, 1], [1, 0]], give[]. - A partial cycle. Courses outside the cycle may be taken, but the answer is still empty, since every course must be taken.
- Reversing the pair.
[a, b]meansbfirst. Putting the arrow the other way gives the reverse dependency order. - Using a plain queue. A queue gives a valid order, but not the one with the smallest ready course first. In the first example a queue would also happen to work, but on other inputs it can take a larger course while a smaller one is ready.
- Pushing a course twice. Only push a course when its count becomes exactly 0, and never after it has been taken.
Testing
findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) -> [0, 1, 2, 3]
findOrder(5, [[1, 4], [0, 4], [2, 3]]) -> [3, 2, 4, 0, 1]
findOrder(3, [[1, 0], [2, 1], [1, 2]]) -> []
findOrder(1, []) -> [0]
findOrder(3, []) -> [0, 1, 2]
findOrder(2, [[0, 1], [1, 0]]) -> []
