Topological Sort — Parallel Courses
↗ LeetCode: Parallel Courses · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Given n courses and prerequisites [a, b] (must take a before b), each semester you can take any courses whose prereqs are met. Return the min number of semesters. -1 if impossible.
Example 1 — n=3, prerequisites=[[1,3],[2,3]] → 2 (sem 1: {1,2}; sem 2: {3}) Example 2 — n=3, prerequisites=[[1,2],[2,3],[3,1]] → -1 (cycle)
Constraints — 1 ≤ n ≤ 5000. Brute simulates semester-by-semester with O(n) scan per semester — O(n²) = 10⁴ ops at n=100 (fine), 10¹⁰ at n=10⁵. Kahn's BFS with per-layer count is O(n+E) = ~10⁶ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DFS with recursion depth
Overestimate. Baseline.
Approach 2 — Kahn's BFS by levels (canonical)
Insight. Toposort in layers — each layer is one semester. Count layers.
java
int minimumSemesters(int n, int[][] relations) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
int[] indeg = new int[n + 1];
for (int[] r : relations) { g.get(r[0]).add(r[1]); indeg[r[1]]++; }
Queue<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);
int sem = 0, taken = 0;
while (!q.isEmpty()) {
sem++;
for (int sz = q.size(); sz > 0; sz--) {
int c = q.poll();
taken++;
for (int nxt : g.get(c))
if (--indeg[nxt] == 0) q.offer(nxt);
}
}
return taken == n ? sem : -1;
}Execution Trace
Step 1 / 2both indeg 0
Complexity — Time O(n + m); Space O(n + m).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DFS depth | O(n + m) | O(n) | valid but subtle |
| Layered BFS | O(n + m) | O(n + m) | canonical |
When to use which
- "Min semesters" / "layers" → layered Kahn's.
- "Order courses list" → flat toposort.
- Course capacity ≤ k per semester → see Parallel Courses III — DP on levels.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems