HardPro challengePythonJavaScriptTypeScript
Graph — Parallel Courses (Topological Sort)
Data StructuresGraphTopological SortBFS
There are n courses labelled 1..n. relations is a list of [prev, next]
pairs meaning **course prev must be finished before course next can
start**.
In one semester you can take any number of courses, as long as every
prerequisite was finished in an earlier semester.
Return the minimum number of semesters needed to take all the courses, or-1 if it is impossible because the prerequisites contain a cycle.
This is a topological sort in layers (Kahn's algorithm): each semester is one
BFS level of the courses whose prerequisites are all done.
Examples
solve(3, [[1, 3], [2, 3]]) → 2 // 1 and 2 together, then 3
solve(3, [[1, 2], [2, 3], [3, 1]]) → -1 // a cycle: nothing can start
solve(4, []) → 1 // no prerequisites, all at onceConstraints
1 <= n <= 5000- Relations may repeat; an unreachable cycle among a *subset* of courses still
makes the whole answer -1.
Sample tests
Test #1Two prerequisites feeding one course
Input: [3,[[1,3],[2,3]]]
Output: 2
Test #2A three-course cycle
Input: [3,[[1,2],[2,3],[3,1]]]
Output: -1
Test #3No prerequisites — everything in one semester
Input: [4,[]]
Output: 1