There are numCourses courses, numbered from 0. Each pair [a, b] in prerequisites means
course b must be taken before course a.
Return an order in which to take every course once, with each course after all of its prerequisites. If several orders work, return any of them. If the prerequisites go round in a loop, so no order works, return an empty list.
Example 1
- Input
- numCourses = 3, prerequisites = [[1, 0], [2, 1]]
- Output
- [0, 1, 2]
Example 2
- Input
- numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
- Output
- [0, 1, 2, 3]
[0, 2, 1, 3] is right too.Example 3
- Input
- numCourses = 2, prerequisites = [[0, 1], [1, 0]]
- Output
- []
Constraints
- 1 ≤
numCourses≤ 2000 prerequisitesholds at most 5000 pairs, each of two different courses, with no pair repeated.
Show the pattern
Topological sort, Graphs
Courses with prerequisites form a directed graph, and a valid order takes each course only after everything that points into it. That is a topological sort, and a cycle makes one impossible.
See topological sort in a visualiserShow the approach
Kahn's algorithm. Count each course's prerequisites (its in-degree) and list which courses each
one unlocks. Start a queue with every course whose count is 0. Repeatedly take a course from the
queue, add it to the order, and lower the count of each course it unlocks, queueing any that
reach 0. If the order ends up with every course, return it; otherwise some courses wait on each
other in a loop, so return [].
Time: O(V + E) · Space: O(V + E)