Advanced Graphs · 147Medium
Course Schedule II
Given numCourses and a list of prerequisite pairs [a, b] meaning b must be taken before a, return any valid ordering in which all courses can be finished. If it is impossible, return an empty array.
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- All prerequisite pairs are distinct.
Examples
findOrder(2, [[1, 0]]) -> [0, 1] findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) -> [0,1,2,3] or [0,2,1,3] findOrder(2, [[1,0],[0,1]]) -> [] // cyclic findOrder(1, []) -> [0] // single course findOrder(3, []) -> [0, 1, 2] // no prerequisites — any order accepted findOrder(3, [[0,1],[1,2]]) -> [2, 1, 0] // a chain forces one order
Edge cases
- A cycle means no ordering exists — return an empty array.
- Courses with no prerequisites can appear anywhere valid.
- Several orderings may be correct; any one is accepted.
Show the target complexity (spoiler)
- Naive
- Trying permutations and validating each is factorial in numCourses.
- Target
- O(V + E) time — topological sort: Kahn's algorithm on in-degrees, or DFS post-order reversed. A result shorter than numCourses proves a cycle.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/19-advanced-graphs/147-course-schedule-ii.js ./practice c 147