Course Schedule
Given course prerequisites, decide whether it is possible to finish every course.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Courses and prerequisites form a directed graph, and all courses can be finished exactly when it has no cycle. Kahn's topological sort (or DFS with visit states) detects this.
Pattern: Graphs. Model the problem as nodes and edges, then pick the traversal: DFS, BFS or a topological order.
Complexity
| Measure | Bound |
|---|---|
| Time | O(V + E) |
| Extra space | O(V + E) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.