Parallel Courses
Problem
You are given an integer n (courses 1..n) and a list of prerequisite relations where each relations[i] = [prev, next] means course prev must be taken before course next. In one semester you may study any number of courses whose prerequisites are all already done. Return the minimum number of semesters needed to finish all courses, or -1 if it is impossible (a cycle exists).
n = 5, relations = [[1,3],[2,3],[3,4],[3,5]]3from collections import deque
def minimum_semesters(n, relations):
indeg = [0] * (n + 1)
adj = [[] for _ in range(n + 1)]
for prev, nxt in relations:
adj[prev].append(nxt)
indeg[nxt] += 1
queue = deque(c for c in range(1, n + 1) if indeg[c] == 0)
semesters, studied = 0, 0
while queue:
semesters += 1
for _ in range(len(queue)):
c = queue.popleft()
studied += 1
for nxt in adj[c]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
return semesters if studied == n else -1function minimumSemesters(n, relations) {
const indeg = new Array(n + 1).fill(0);
const adj = Array.from({ length: n + 1 }, () => []);
for (const [prev, nxt] of relations) {
adj[prev].push(nxt);
indeg[nxt]++;
}
let queue = [];
for (let c = 1; c <= n; c++) if (indeg[c] === 0) queue.push(c);
let semesters = 0, studied = 0;
while (queue.length) {
semesters++;
const next = [];
for (const c of queue) {
studied++;
for (const nxt of adj[c]) {
if (--indeg[nxt] === 0) next.push(nxt);
}
}
queue = next;
}
return studied === n ? semesters : -1;
}class Solution {
public int minimumSemesters(int n, int[][] relations) {
int[] indeg = new int[n + 1];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] r : relations) { adj.get(r[0]).add(r[1]); indeg[r[1]]++; }
Deque<Integer> queue = new ArrayDeque<>();
for (int c = 1; c <= n; c++) if (indeg[c] == 0) queue.add(c);
int semesters = 0, studied = 0;
while (!queue.isEmpty()) {
semesters++;
for (int sz = queue.size(); sz > 0; sz--) {
int c = queue.poll();
studied++;
for (int nxt : adj.get(c))
if (--indeg[nxt] == 0) queue.add(nxt);
}
}
return studied == n ? semesters : -1;
}
}int minimumSemesters(int n, vector<vector<int>>& relations) {
vector<int> indeg(n + 1, 0);
vector<vector<int>> adj(n + 1);
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 semesters = 0, studied = 0;
while (!q.empty()) {
semesters++;
for (int sz = q.size(); sz > 0; sz--) {
int c = q.front(); q.pop();
studied++;
for (int nxt : adj[c])
if (--indeg[nxt] == 0) q.push(nxt);
}
}
return studied == n ? semesters : -1;
}Explanation
Each semester you can take every course whose prerequisites are already done, so this is really about peeling the dependency graph one layer at a time. The number of layers is the number of semesters, and we count them with a topological sort (Kahn's algorithm).
We track each course's indeg — how many prerequisites it still needs. Courses with indeg == 0 have nothing blocking them, so they go into the queue as the first semester's batch.
The key move is processing the queue one whole semester at a time: we snapshot the current queue size, take all those courses together (semesters++), and for each finished course we drop the indeg of its dependents. Any dependent that reaches 0 becomes available for the next semester.
If we finish all n courses, we return the semester count. If studied != n, some courses were trapped in a cycle and never reached zero in-degree, so we return -1.
Example: n=5, relations [[1,3],[2,3],[3,4],[3,5]]. Semester 1 takes 1 and 2, semester 2 takes 3, semester 3 takes 4 and 5 — answer 3.