NeetCode #609LC-1136MediumGraphsNC Algo100
← Back to All Problems#609 · #1136 · Parallel Courses(并行课程)
📌 Problem Statement & Constraints
You are given
n courses and relations where relations[i] = [a, b] means course a must be taken before b. In one semester you may take any number of courses whose prerequisites are all satisfied. Return the minimum number of semesters, or -1 if impossible. Constraints: 1 <= n <= 5000, 1 <= relations.length <= 5000.💡 Core Algorithmic Approaches
- This is a topological sort where the answer is the number of layers (Kahn's algorithm processed level by level).
- Each level contains all courses whose in-degree has just reached 0.
- If the total taken is less than
n, a cycle exists and the answer is -1. - The layering is what makes it the longest path in the DAG rather than just any topological order.
💻 Benchmark Python3 Implementation
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
from collections import defaultdict, deque
g = defaultdict(list)
indeg = [0] * (n + 1) # courses are 1-indexed
for a, b in relations:
g[a].append(b)
indeg[b] += 1
q = deque(i for i in range(1, n + 1) if indeg[i] == 0)
semesters = 0
taken = 0
while q:
semesters += 1 # one semester per BFS layer
for _ in range(len(q)):
node = q.popleft()
taken += 1
for nxt in g[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return semesters if taken == n else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V + E) for the graph.
⚠️ Interview Pitfalls & Follow-ups
- Returning the number of nodes processed: the answer is the number of layers.
- Not checking the taken count: a cycle leaves some courses untaken.
- Using 0-indexed arrays: the courses are labelled
1..n. - Assuming one course per semester: any number can be taken when prerequisites allow.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.