There are numCourses courses labelled 0 to numCourses - 1, and prerequisites[i] = [a, b] means course b must be taken before course a. Return any order in which you can take all the courses. If it is impossible, return an empty array.
[0,2,1,3] is also accepted.- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- All pairs are distinct
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Any valid answer is a topological order of the graph with edges b -> a. Kahn's algorithm produces one directly: a course enters the queue only after all its prerequisites have been popped, so the pop order respects every prerequisite. If a cycle exists, the courses on it never reach in-degree 0, the order comes out short, and we return an empty array.
Algorithm
- Build the adjacency list
b -> aand the in-degree of each course. - Queue every course with in-degree 0.
- Pop a course, append it to
order, and decrease the in-degree of the courses it unlocks; queue those that reach 0. - Return
orderif its length isnumCourses, else[].
O(V + E)Space: O(V + E)class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: graph = [[] for _ in range(numCourses)] indeg = [0] * numCourses for a, b in prerequisites: graph[b].append(a) # b -> a indeg[a] += 1 queue = deque(i for i in range(numCourses) if indeg[i] == 0) order = [] while queue: course = queue.popleft() order.append(course) # pop order is a valid schedule for nxt in graph[course]: indeg[nxt] -= 1 if indeg[nxt] == 0: queue.append(nxt) return order if len(order) == numCourses else [] # short order means a cycle