1136. Parallel Courses
Asked at Netflix, Snowflake
Difficulty
Medium
Time
O(V + E)
Space
O(V + E)
Pattern
Graph
Companies
2
Problem
You have n courses, numbered 1 to n. You also get a list of relations, where each pair [a, b] means course a must be finished before course b.
Courses run in semesters. In one semester you may take any number of courses at the same time, as long as every prerequisite of each course was already finished in an earlier semester. So all courses you pick in the same semester must be independent of each other.
Return the minimum number of semesters needed to finish all n courses. If some courses depend on each other in a cycle, no valid order exists — return -1 in that case.
Who can be taken when
Constraints
- ●
1 <= n <= 5000 - ●
1 <= relations.length <= 5000 - ●
relations[i].length == 2 - ●
1 <= prevCoursei, nextCoursei <= n - ●
prevCoursei != nextCoursei - ●
All the pairs [prevCoursei, nextCoursei] are unique.
Examples
n = 3, relations = [[1,3],[2,3]]2n = 3, relations = [[1,2],[2,3],[3,1]]-1Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Netflix | Medium | View all Netflix questions → |
| Snowflake | Medium | View all Snowflake 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).
Kahn's BFS by levels
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
O(V + E) timedef 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 runs in O(V + E) time and O(V + E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Parallel Courses?
Parallel Courses is asked at Netflix, Snowflake. 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.