Parallel Courses
Problem Statement
There are n courses labelled 1..n and a list relations where relations[i] = [prevCourse, nextCourse] means prevCourse must be completed before nextCourse.
In one semester, you may take all courses whose prerequisites have already been completed. Return the minimum number of semesters needed to complete every course, or -1 if it is impossible because the prerequisite graph contains a cycle.
Input
An integer n and directed edges relations from prerequisite course to dependent course. Course labels are 1-based.
Output
An integer: the minimum number of semesters to finish all courses, or -1 if a cycle makes completion impossible.
Constraints
- •
1 <= n <= 5000 - •
1 <= relations.length <= 5000 - •
relations[i].length == 2 - •
1 <= prevCourse, nextCourse <= n - •
prevCourse != nextCourse - •
All relation pairs are unique
Examples
Example 1
n = 3, relations = [[1,3],[2,3]]
2Example 2
n = 3, relations = [[1,2],[2,3],[3,1]]
-1Example 3
n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]]
3Learning Objectives
- Interpret each layer of Kahn's BFS as one semester of parallel work.
- Minimise time by taking every currently available course immediately.
- Detect cycles with the same processed-count check used in Course Schedule.
- Handle 1-based course labels cleanly without off-by-one errors.
Intuition
This is Course Schedule with a clock. The courses with zero remaining prerequisites are exactly the courses you can take now. Since there is no limit on how many available courses you can take in a semester, the greedy move is forced: take all of them immediately. Waiting cannot help, because delaying an available course can only delay courses that depend on it.
That turns Kahn's algorithm into a level-order BFS. The initial zero-indegree queue is semester 1. After processing the entire current queue, newly unlocked courses form the next semester. Counting BFS layers gives the minimum number of semesters.
If a cycle exists, the queue eventually empties before all courses are processed. The remaining courses are waiting on each other, so the correct answer is -1.
Common mistakes
- ×Incrementing semesters for every course instead of every BFS layer.
- ×Processing newly unlocked courses in the same semester. A course unlocked by work this semester can only be taken next semester.
- ×Forgetting that course labels are 1..n, not 0..n - 1.
- ×Returning the semester count without checking whether all courses were processed.
- ×Taking only one zero-indegree course per semester, which misses the parallelism and overestimates the answer.
Algorithm Explanation
- Build adjacency lists from each prerequisite course to the courses it unlocks, and count indegrees.
- Enqueue every course with indegree 0. These courses can all be taken in semester 1.
- While the queue is not empty, record its current size. That fixed-size batch is one semester.
- Process exactly that many courses, decrementing indegrees of dependent courses. Any course that becomes zero-indegree is enqueued for the next semester.
- Increment the semester count after each batch and track how many courses were processed.
- Return semesters if processed == n; otherwise return -1 because a cycle prevented completion.
Solutions
Solution: Level-order Kahn's BFS
Run Kahn's algorithm by layers instead of individual nodes. Each layer contains all courses currently available, so each layer corresponds to one semester.
Step-by-step
- Allocate graph for labels 1..n and indegree for the same range.
- Add every relation prev → next and increment indegree[next].
- Queue all courses with indegree 0.
- For each semester, process the queue's current size only. Those courses are taken together.
- Newly zero-indegree courses are enqueued but not processed until the next outer loop iteration.
- After BFS, return the number of layers if all n courses were processed; otherwise return -1.
O(V + E)
O(V + E)
V is n and E is relations.length; adjacency, indegree, and queue are linear.
Java implementation
Dry Run
Sample input
n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]]. Indegree: 1=0, 2=0, 3=0, 4=1, 5=4.
| Semester | Courses taken | Edges relaxed | New queue | Completed total |
|---|---|---|---|---|
| 1 | [1,2,3] | 1→5, 2→5, 3→5, 3→4 | [4] | 3 |
| 2 | [4] | 4→5 | [5] | 4 |
| 3 | [5] | none | [] | 5 |
The BFS has three layers, so three semesters are necessary and sufficient. Course 5 cannot be taken until semester 3 because course 4 is one of its prerequisites and only unlocks after semester 1.
Interview Tips
Emphasise the greedy proof: because unlimited available courses can be taken together, there is never a reason to postpone a zero-indegree course. The implementation detail interviewers watch for is the fixed queue size per semester; without that boundary, you accidentally take newly unlocked courses too early. End with the processed-count cycle check, exactly like Course Schedule.
Likely follow-ups
- What if each semester can contain at most k courses? The problem becomes harder and may need bitmask DP for small n.
- What if each course has a duration and you want the earliest completion time? Use longest path DP on a DAG.
- Return the actual list of courses taken in each semester.
- How would you update the answer if a new prerequisite relation is added?
Similar Problems
Key Takeaways
- When all available courses can be taken together, each Kahn BFS layer is one semester.
- Process a fixed queue size per layer so newly unlocked courses wait for the next semester.
- Taking all zero-indegree courses immediately is optimal because delaying cannot unlock anything earlier.
- If processed courses are fewer than n, a cycle makes completion impossible.