medium

Course Schedule

There are n courses, and a list of pairs [a, b] meaning course b must be completed before course a. Determine whether it is possible to finish all courses.

Constraints
  • 1 ≤ n ≤ 2000
  • 0 ≤ prerequisites.length ≤ 5000
  • All pairs distinct
Examples
in: n = 2, prerequisites = [[1,0]]
out: true
in: n = 2, prerequisites = [[1,0],[0,1]]
out: false
Recognition clues
  • Prerequisites = directed edges
  • Feasible iff the dependency graph has no cycle
  • Peel off nodes with in-degree zero
Pattern
Topological Sort

Constraints of the form "A before B" are edges in a directed graph; a valid schedule exists exactly when the graph has no cycle, and any topological order is a valid schedule. Kahn's algorithm (peel off zero in-degree nodes) also detects impossibility: if it stops before emitting every node, a cycle remains.

Topological SortKahn's AlgorithmCycle DetectionDAG (Directed Acyclic Graph)
Solution

Build a directed graph from prerequisite to course and compute in-degrees. Run Kahn's algorithm: enqueue all courses with in-degree 0, repeatedly dequeue one, count it as taken and decrement the in-degree of each dependent, enqueuing those that reach 0. If the number of dequeued courses equals n the graph is a DAG and all courses can be finished; otherwise the leftovers form a cycle.

time O(V + E)space O(V + E)
Alternative approaches
  • DFS with three colours (unvisited/in-progress/done) detects a cycle when a grey node is revisited and also yields an order in reverse post-order.
Code it yourself
Solve in
Hints:
Learn Topological Sort▶ VisualizeMock interview version