Parallel Courses — Solution in Python, Java & C++
Parallel Courses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Parallel Courses is a medium coding problem on breadth-first search, graph and topological sort, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Graph, Topological Sort
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n courses numbered 1 … n. relations[i] = [prev, next] means course prev must be taken before course next.
In one semester you may take any number of courses, as long as every prerequisite of each was taken in an earlier semester. Return the minimum number of semesters needed to take all n courses, or -1 if that is impossible.
Example 1
Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: Take courses 1 and 2 together, then course 3.
Example 2
Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: The prerequisites form a cycle.
Example 3
Input: n = 4, relations = []
Output: 1
Explanation: Everything can be taken at once.
Constraints
1 <= n <= 50001 <= relations.length <= 5000relations[i].length == 21 <= prev, next <= nprev != nextAll the pairs are unique.
Hints for Parallel Courses
Hint 1
Because a semester holds any number of courses, take everything whose prerequisites are done.
Hint 2
That is a topological sort processed one whole layer at a time.
Hint 3
If some course is never freed, the prerequisites contain a cycle.
How to solve Parallel Courses
Run Kahn's algorithm, but peel a whole layer per round. The number of rounds is the number of semesters; if fewer than n courses are ever taken, a cycle blocks the rest.
Approach
- Count in-degrees and queue every course with none.
- Each round, take the entire current queue as one semester and decrement its successors' in-degrees.
- Courses reaching in-degree 0 form the next round's queue.
- Return the round count if all
ncourses were taken, and-1otherwise.
Why it works
Taking every available course immediately is optimal because a course can never be a reason to delay another — courses are free and unlimited, so there is no trade-off to weigh. That makes the layered peel a lower bound as well as achievable, and the layer number of a course is the length of its longest prerequisite chain.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Courses are numbered from 1; size the arrays accordingly.
- A cycle shows as a shortfall in the taken count, not as an error during the sweep.
- Peeling one course at a time counts courses, not semesters.
Reference solution
Python
from typing import List
def minimumSemesters(n: int, relations: List[List[int]]) -> int:
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for a, b in relations:
adj[a].append(b)
indeg[b] += 1
q = [i for i in range(1, n + 1) if indeg[i] == 0]
taken = 0
sem = 0
while q:
sem += 1
nq = []
for u in q:
taken += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
nq.append(v)
q = nq
return sem if taken == n else -1Java
public static 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]]++;
}
List<Integer> q = new ArrayList<>();
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.add(i);
int taken = 0, sem = 0;
while (!q.isEmpty()) {
sem++;
List<Integer> nq = new ArrayList<>();
for (int u : q) {
taken++;
for (int v : adj.get(u)) {
if (--indeg[v] == 0) nq.add(v);
}
}
q = nq;
}
return taken == n ? sem : -1;
}C++
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]]++;
}
vector<int> q;
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push_back(i);
int taken = 0, sem = 0;
while (!q.empty()) {
sem++;
vector<int> nq;
for (int u : q) {
taken++;
for (int v : adj[u]) {
if (--indeg[v] == 0) nq.push_back(v);
}
}
q = nq;
}
return taken == n ? sem : -1;
}JavaScript
var minimumSemesters = function(n, relations) {
var i;
var adj = [], indeg = [];
for (i = 0; i <= n; i++) { adj.push([]); indeg.push(0); }
for (i = 0; i < relations.length; i++) {
adj[relations[i][0]].push(relations[i][1]);
indeg[relations[i][1]]++;
}
var q = [];
for (i = 1; i <= n; i++) if (indeg[i] === 0) q.push(i);
var taken = 0, sem = 0;
while (q.length > 0) {
sem++;
var nq = [];
for (var k = 0; k < q.length; k++) {
var u = q[k];
taken++;
for (var t = 0; t < adj[u].length; t++) {
var v = adj[u][t];
indeg[v]--;
if (indeg[v] === 0) nq.push(v);
}
}
q = nq;
}
return taken === n ? sem : -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Graph Data Structure