Course Schedule
Medium · Graphs · Graph · Topological Sort · DFS · BFS
Problem
There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] in prerequisites means b must be taken before a.
Return whether every course can be completed.
Examples
Input: numCourses = 2, prerequisites = [[1,0]] Output: True
Take 0, then 1.
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: False
Each needs the other first — a cycle.
Constraints
- 1 <= numCourses <= 2000
- 0 <= len(prerequisites) <= 5000
- Pairs are distinct
Approaches
- DFS with three-state colouring — time O(V + E), space O(V + E)
Related problems
Start free on Cariara · Coding problems · System design studio
