The problem
As in Course Schedule: numCourses courses, and pairs [a, b] meaning b must come before a.
Return an order in which to take all the courses. Any valid order will do; if none exists, return an empty array.
Examples
01
- Input
numCourses = 2, prerequisites = [[1, 0]]
- Output
[0, 1]
02
- Input
numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
- Output
[0, 1, 2, 3]
03
- Input
numCourses = 1, prerequisites = []
- Output
[0]
Constraints
- 1 ≤ numCourses ≤ 2000
- Every pair is distinct, and a ≠ b.
The idea
An order in which every arrow points forward is a topological order. Kahn’s algorithm produces one: the order in which it takes the courses.
Write each course down as it is taken — a course is only taken once all its prerequisites have been. If the list ends shorter than numCourses, the missing courses are stuck on a cycle, and there is no valid order.
- Time
- O(V + E)
- Space
- O(V + E)
Solution · every language run against every case
class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: # Kahn's algorithm: take any course with no unmet prerequisite, then update the rest. after = [[] for _ in range(numCourses)] # course -> the courses that need it need = [0] * numCourses # course -> how many prerequisites it still waits for for course, pre in prerequisites: after[pre].append(course) need[course] += 1 order = [c for c in range(numCourses) if need[c] == 0] for c in order: # the list grows as courses become ready for nxt in after[c]: need[nxt] -= 1 if need[nxt] == 0: order.append(nxt) return order if len(order) == numCourses else [] # short means a cycle