Parallel Courses
Asked at Netflix
Problem
You are given an integer n which represents the number of courses labeled from 1 to n. You are also given a list of prerequisites where prerequisites[i] = [ai, bi] means course bi must be taken before course ai. Find the minimum number of semesters needed to complete all courses if you can take any number of courses in parallel, provided their prerequisites are satisfied. Return -1 if it is impossible to complete all courses.
Asked At
| Company | Difficulty | |
|---|---|---|
| Netflix | MEDIUM | View all Netflix questions → |
How to Think About It
Model the problem as a directed graph where edges go from prerequisite to dependent course.
Detect cycles using Kahn's algorithm (BFS-based topological sort) — if not all courses are visited, a cycle exists.
Compute in-degrees for all nodes and start BFS from nodes with in-degree 0.
Each BFS level represents one semester — all courses at the same level can be taken in parallel.
Track the number of BFS levels traversed; this equals the minimum semesters required.
Optimal Approach
Build an adjacency list and compute in-degrees. Initialize a queue with all courses having in-degree 0 (no prerequisites). Perform BFS: for each level, dequeue all current courses (they can be taken in parallel), decrement in-degrees of their neighbors, and enqueue neighbors whose in-degree becomes 0. Increment the semester count for each BFS level. If the total courses processed is less than n, a cycle exists and we return -1. Time complexity is O(V + E).
What Trips People Up in Real Interviews
Clarify: courses are labeled 1 to n, and every course must be taken exactly once.
Edge case: no prerequisites — all courses can be taken in one semester, answer is 1.
Edge case: a cycle exists (e.g., 1→2→1) — return -1.
Edge case: linear chain (1→2→3→4) — each course depends on the previous, answer is n semesters.
Explain why BFS (Kahn's) is preferred over DFS here — BFS naturally processes courses level by level, which maps to semesters.
Solution Code
def minimumSemesters(n, relations):
from collections import deque, defaultdict
graph = defaultdict(list)
in_degree = [0] * (n + 1)
for dest, src in relations:
graph[src].append(dest)
in_degree[dest] += 1
queue = deque()
for i in range(1, n + 1):
if in_degree[i] == 0:
queue.append(i)
semesters = 0
visited = 0
while queue:
semesters += 1
size = len(queue)
for _ in range(size):
node = queue.popleft()
visited += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return semesters if visited == n else -1Frequently Asked Questions
What is the Parallel Courses problem?
You are given an integer n which represents the number of courses labeled from 1 to n. You are also given a list of prerequisites where prerequisites[i] = [ai, bi] means course bi must be taken before course ai. Find the minimum number of semesters needed to complete all courses if you can take any number of courses in parallel, provided their prerequisites are satisfied. Return -1 if it is impossible to complete all courses.
How do you solve Parallel Courses?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Parallel Courses?
Parallel Courses is asked at Netflix. It is a medium difficulty problem.
What are common mistakes on Parallel Courses?
- Clarify: courses are labeled 1 to n, and every course must be taken exactly once.
- Edge case: no prerequisites — all courses can be taken in one semester, answer is 1.
- Edge case: a cycle exists (e.g., 1→2→1) — return -1.
- Edge case: linear chain (1→2→3→4) — each course depends on the previous, answer is n semesters.
- Explain why BFS (Kahn's) is preferred over DFS here — BFS naturally processes courses level by level, which maps to semesters.