We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
You are given n courses labelled 1 to n and a list of relations where relations[i] = [prev, next] means prev must be taken before next.
In one semester you may take any number of courses at once, as long as every prerequisite was taken in an earlier semester.
Return the minimum number of semesters needed to take all courses, or -1 if it is impossible.
A medium topological sort problem, graded against 6 test cases (3 of them hidden).
Ordering a directed acyclic graph so every dependency comes first.
Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"
More Topological Sort problems →Because a semester can hold unlimited courses, the answer is the number of levels in the dependency graph - equivalently the length of its longest prerequisite chain.
Run Kahn's algorithm, but process a whole frontier at a time: every course currently at indegree 0 is takeable this semester, so consume them all, relax their outgoing edges, and collect whatever reaches indegree 0 as the next semester's frontier. Increment a counter once per round.
This is exactly BFS level-order traversal applied to a DAG, and it is why the answer equals the longest chain: a course cannot appear before every prerequisite has been consumed in an earlier round.
Two traps. First, count rounds, not courses - a natural but wrong instinct is to increment inside the inner loop. Second, courses are numbered 1 to n, not 0 to n-1, so arrays need `n + 1` slots and the initial scan runs from 1; an off-by-one here silently reports a phantom course at index 0 that never becomes available.
As with Kahn generally, a cycle shows up as courses that never reach indegree 0, so compare the total consumed against `n`.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.