Course Schedule II
Medium· Topological Sort
Problem
Same setup as Course Schedule, but now return an order in which all courses can be taken. If several orders work, return any of them; if none exists, return an empty array.
Examples
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
[0,2,1,3] is also accepted.
Input: numCourses = 2, prerequisites = [[0,1],[1,0]]
Output: []
Constraints
- • 1 <= numCourses <= 2000
- • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- • All pairs are distinct
Hints & approach
Hint 1
This is asking for a topological ordering.
Hint 2
The order in which Kahn's algorithm dequeues nodes is already a valid answer.
Approachtry the hints first
Run Kahn's algorithm: compute in-degrees, seed a queue with zero in-degree courses, and append each popped course to the output while decrementing its dependants. If the output ends up shorter than numCourses, a cycle blocked some courses, so return an empty array. The DFS alternative appends nodes in post-order and reverses the list at the end.
Time O(V + E) · Space O(V + E)