Course Schedule
Course Schedule is a medium Graphs problem from the Blind 75. The key pattern is topological sort, and a good solution runs in O(V + E) time.
Problem
Given a course count and prerequisite pairs [course, prerequisite], determine whether every course can be completed.
Examples
Example 1
Input
{"courses":4,"prerequisites":[[1,0],[2,1],[3,2]]}Output
trueExample 2
Input
{"courses":2,"prerequisites":[[1,0]]}Output
trueExample 3
Input
{"courses":3,"prerequisites":[[0,1],[1,2],[2,0]]}Output
falseApproach
Count prerequisites per course and repeatedly take courses with none left (Kahn's algorithm). If every course gets taken, there is no cycle.
| Pattern | Topological sort |
|---|---|
| Time | O(V + E) |
| Space | O(V + E) |
Watch out for
Pairs are [course, prerequisite], so the edge points from prerequisite to course.