Course Schedule
The problem
There are n courses labeled 0 through n−1. Each pair [a, b] requires taking b before a. Decide whether all courses can be completed.
Example
n = 3, prerequisites = [[1, 0], [2, 1]] → true; adding [0, 2] makes it false.
Need a hint?
An ordering exists exactly when the dependency graph has no directed cycle.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Build outgoing edges and indegrees. Enqueue all zero-indegree courses. Repeatedly remove a course, count it, and decrease its dependents’ indegrees, enqueuing newly ready courses. All courses are possible if the removed count equals n.
Complexity
O(V + E) time and space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.