Parallel Courses
Parallel Courses is a medium graphs problem solved with the topological sort pattern.
The best approach, optimal (kahn's algorithm, level by level), runs in O(n + m) time and O(n + m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate semester by semester) up.
Problem
There are n courses labelled 1 to n. Each entry relations[i] = [prev, next] says that course prev must be completed in an earlier semester than course next.
In one semester you may take any number of courses, as long as all of their prerequisites were finished in previous semesters. Return the minimum number of semesters needed to complete every course, or -1 if it is impossible because some prerequisites form a cycle.
Examples
Example 1
- Input
n = 4, relations = [[1, 3], [2, 3], [3, 4]]- Output
3- Why
- Semester 1: courses 1 and 2. Semester 2: course 3. Semester 3: course 4.
Example 2
- Input
n = 5, relations = [[1, 2], [2, 4], [4, 1], [3, 5]]- Output
-1- Why
- Courses 1, 2 and 4 wait on each other in a loop, so none of them can ever be started.
Example 3
- Input
n = 3, relations = []- Output
1- Why
- With no prerequisites, all three courses fit in the first semester.
Constraints
1 <= n <= 50000 <= relations.length <= 5000relations[i] = [prev, next]with1 <= prev, next <= nandprev != next- All pairs in
relationsare distinct.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (simulate semester by semester) | O(n · (n + m)) | O(n) |
| Optimal (Kahn's algorithm, level by level) | O(n + m) | O(n + m) |
1Brute force (simulate semester by semester)
O(n · (n + m))Up to n semesters, each scanning all courses and all m relations.O(n)A few arrays of size n.Repeat: look at every course not yet taken and check, by scanning all relations, whether all its prerequisites were finished in an earlier semester. Take all such courses at once. If a semester adds nothing while courses remain, the remaining ones are stuck in a cycle.
- Keep a
donearray and a counter of finished courses. - Each semester, mark a course ready if no relation [p, c] has p unfinished (judged by the state at the start of the semester).
- If no course is ready, return -1; otherwise mark them done and add one semester.
- Stop when all n courses are done.
class Solution {
public int minimumSemesters(int n, int[][] relations) {
boolean[] done = new boolean[n + 1];
int finished = 0, semesters = 0;
while (finished < n) {
boolean[] blocked = new boolean[n + 1];
for (int[] r : relations) {
if (!done[r[0]]) blocked[r[1]] = true;
}
List<Integer> ready = new ArrayList<>();
for (int c = 1; c <= n; c++) {
if (!done[c] && !blocked[c]) ready.add(c);
}
if (ready.isEmpty()) return -1;
for (int c : ready) done[c] = true;
finished += ready.size();
semesters++;
}
return semesters;
}
}class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
done = [False] * (n + 1)
finished = semesters = 0
while finished < n:
blocked = [False] * (n + 1)
for p, c in relations:
if not done[p]:
blocked[c] = True
ready = [c for c in range(1, n + 1) if not done[c] and not blocked[c]]
if not ready:
return -1
for c in ready:
done[c] = True
finished += len(ready)
semesters += 1
return semestersclass Solution {
public:
int minimumSemesters(int n, vector<vector<int>>& relations) {
vector<bool> done(n + 1, false);
int finished = 0, semesters = 0;
while (finished < n) {
vector<bool> blocked(n + 1, false);
for (auto& r : relations) {
if (!done[r[0]]) blocked[r[1]] = true;
}
vector<int> ready;
for (int c = 1; c <= n; c++) {
if (!done[c] && !blocked[c]) ready.push_back(c);
}
if (ready.empty()) return -1;
for (int c : ready) done[c] = true;
finished += ready.size();
semesters++;
}
return semesters;
}
};function minimumSemesters(n, relations) {
const done = new Array(n + 1).fill(false);
let finished = 0, semesters = 0;
while (finished < n) {
const blocked = new Array(n + 1).fill(false);
for (const [p, c] of relations) {
if (!done[p]) blocked[c] = true;
}
const ready = [];
for (let c = 1; c <= n; c++) {
if (!done[c] && !blocked[c]) ready.push(c);
}
if (ready.length === 0) return -1;
for (const c of ready) done[c] = true;
finished += ready.length;
semesters++;
}
return semesters;
}2Optimal (Kahn's algorithm, level by level)
O(n + m)Every course is dequeued once and every relation is relaxed once.O(n + m)Adjacency lists, in-degree array and the queue.Build the graph and the in-degree of every course. Start a queue with all in-degree-zero courses; that is semester 1. Pop a whole level at a time, lower the in-degree of each successor, and push successors that reach zero into the next level. Count the levels and the courses taken; if fewer than n courses were taken, a cycle blocked the rest.
- Build adjacency lists
prev -> nextand the in-degree array. - Queue every course with in-degree 0.
- While the queue is not empty: semesters++, and process exactly the current queue size, decrementing in-degrees of successors and enqueuing those that hit 0.
- Return semesters if every course was dequeued, otherwise -1.
class Solution {
public int minimumSemesters(int n, int[][] relations) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n + 1];
for (int[] r : relations) {
adj.get(r[0]).add(r[1]);
indeg[r[1]]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int c = 1; c <= n; c++) if (indeg[c] == 0) q.add(c);
int taken = 0, semesters = 0;
while (!q.isEmpty()) {
semesters++;
for (int size = q.size(); size > 0; size--) {
int c = q.poll();
taken++;
for (int nx : adj.get(c)) {
if (--indeg[nx] == 0) q.add(nx);
}
}
}
return taken == n ? semesters : -1;
}
}class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for p, c in relations:
adj[p].append(c)
indeg[c] += 1
q = deque(c for c in range(1, n + 1) if indeg[c] == 0)
taken = semesters = 0
while q:
semesters += 1
for _ in range(len(q)):
c = q.popleft()
taken += 1
for nx in adj[c]:
indeg[nx] -= 1
if indeg[nx] == 0:
q.append(nx)
return semesters if taken == n else -1class Solution {
public:
int minimumSemesters(int n, vector<vector<int>>& relations) {
vector<vector<int>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (auto& r : relations) {
adj[r[0]].push_back(r[1]);
indeg[r[1]]++;
}
queue<int> q;
for (int c = 1; c <= n; c++) if (indeg[c] == 0) q.push(c);
int taken = 0, semesters = 0;
while (!q.empty()) {
semesters++;
for (int size = q.size(); size > 0; size--) {
int c = q.front();
q.pop();
taken++;
for (int nx : adj[c]) {
if (--indeg[nx] == 0) q.push(nx);
}
}
}
return taken == n ? semesters : -1;
}
};function minimumSemesters(n, relations) {
const adj = Array.from({ length: n + 1 }, () => []);
const indeg = new Array(n + 1).fill(0);
for (const [p, c] of relations) {
adj[p].push(c);
indeg[c]++;
}
let level = [];
for (let c = 1; c <= n; c++) if (indeg[c] === 0) level.push(c);
let taken = 0, semesters = 0;
while (level.length > 0) {
semesters++;
const next = [];
for (const c of level) {
taken++;
for (const nx of adj[c]) {
if (--indeg[nx] === 0) next.push(nx);
}
}
level = next;
}
return taken === n ? semesters : -1;
}Edge cases to test
- No relations at all: the answer is 1
- A single long chain 1 -> 2 -> ... -> n: the answer is n
- A cycle in one part of the graph while other parts are fine: still -1
- A course with many prerequisites finishing on different semesters: it waits for the latest one
Hints
Hint 1
Draw an edge prev -> next. In each semester you can take every course whose prerequisites are all done.
Hint 2
Count, for every course, how many prerequisites are still missing (its in-degree). The courses with zero form the first semester.
Hint 3
Process the graph level by level like a BFS (Kahn's algorithm). The number of levels is the answer; if some course is never reached, there is a cycle.
FAQ
What is the best time complexity for Parallel Courses?
Optimal (Kahn's algorithm, level by level) runs in O(n + m) time and O(n + m) extra space. Every course is dequeued once and every relation is relaxed once.
Which pattern does Parallel Courses use?
It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.
Is there a brute force solution for Parallel Courses?
Yes. Brute force (simulate semester by semester) takes O(n · (n + m)) time and O(n) space. Repeat: look at every course not yet taken and check, by scanning all relations, whether all its prerequisites were finished in an earlier semester.
Which edge cases should I test for Parallel Courses?
No relations at all: the answer is 1; A single long chain 1 - 2 - ... - n: the answer is n; A cycle in one part of the graph while other parts are fine: still -1; A course with many prerequisites finishing on different semesters: it waits for the latest one.