Course Schedule II
Medium · Graphs · Graph · Topological Sort · BFS · DFS
Problem
There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] means b must be taken before a.
Return any order in which every course can be taken. If no such order exists, return an empty list.
Examples
Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1]
0 unlocks 1.
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3]
[0,2,1,3] is equally valid — any order respecting the edges is accepted.
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: []
A cycle.
Constraints
- 1 <= numCourses <= 2000
- 0 <= len(prerequisites) <= numCourses * (numCourses - 1)
- Pairs are distinct
Approaches
- DFS post-order, reversed — time O(V + E), space O(V + E)
Related problems
Start free on Cariara · Coding problems · System design studio
