Parallel Courses
01 · Problem
There are n courses labelled 1 to n. Each relations[i] = [prev, next] means course prev must be finished in an earlier semester than course next.
In a single semester you may take any number of courses, as long as every prerequisite of each of them was completed in a previous semester.
Return the minimum number of semesters needed to finish all n courses. If the prerequisites contain a cycle, so that it is impossible to finish everything, return -1.
02 · Examples
n = 3, relations = [[1,3],[2,3]]
2
Take courses 1 and 2 in the first semester, then course 3 in the second.
n = 3, relations = [[1,2],[2,3],[3,1]]
-1
Courses 1, 2 and 3 depend on each other in a cycle, so none of them can ever be started.
n = 5, relations = [[1,2],[2,3],[1,4],[4,5],[3,5]]
4
The longest prerequisite chain is 1 -> 2 -> 3 -> 5, which needs 4 semesters. Course 4 can be taken alongside course 2 or 3.
03 · Constraints
- 011 <= n <= 5000
- 020 <= relations.length <= 5000
- 03relations[i].length == 2
- 041 <= prev, next <= n and prev != next
- 05All relation pairs are distinct
04 · Optimal complexity
- Time
- O(n + e)
- Space
- O(n + e)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.