Prerequisites
Before attempting this problem, you should be comfortable with:
- Graph Representation (Adjacency List) - Required to model course dependencies as a directed graph
- Topological Sort (Kahn's Algorithm) - Primary technique using BFS to process nodes level by level
- In-degree Tracking - Understanding how to count and update incoming edges for each node
- Cycle Detection in Directed Graphs - Needed to identify impossible course schedules
- Depth-First Search (DFS) - Alternative approach for both cycle detection and longest path computation
1. Breadth-First Search (Kahn's Algorithm)
Intuition
This problem asks for the minimum number of semesters to complete all courses with prerequisites. Since we can take multiple courses in parallel each semester (as long as their prerequisites are met), this naturally maps to a topological sort problem where we process courses level by level.
Kahn's algorithm works perfectly here. We start with courses that have no prerequisites (in-degree of 0) and take them all in the first semester. Then we remove their outgoing edges, which may unlock new courses for the next semester. Each BFS level represents one semester.
If we cannot complete all courses (due to a cycle), we return -1.
Algorithm
- Build an adjacency list and compute in-degrees for all courses.
- Initialize a queue with all courses having in-degree
0(no prerequisites). - Process the queue level by level, where each level represents a semester:
- For each course in the current level, decrement the in-degree of its dependent courses.
- Add any course whose in-degree becomes
0to the next level. - Increment the semester counter.
- If all courses are processed, return the number of semesters. Otherwise, return
-1.
class Solution:
def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
graph = {i: [] for i in range(1, N + 1)}
in_count = {i: 0 for i in range(1, N + 1)} # or in-degree
for start_node, end_node in relations:
graph[start_node].append(end_node)
in_count[end_node] += 1
queue = []
# we use list here since we are not
# popping from the front in this code
for node in graph:
if in_count[node] == 0:
queue.append(node)
step = 0
studied_count = 0
# start learning with BFS
while queue:
# start new semester
step += 1
next_queue = []
for node in queue:
studied_count += 1
end_nodes = graph[node]
for end_node in end_nodes:
in_count[end_node] -= 1
# if all prerequisite courses learned
if in_count[end_node] == 0:
next_queue.append(end_node)
queue = next_queue
return step if studied_count == N else -1Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of
relationsand is the number of courses.
2. Depth-First Search: Check for Cycles + Find Longest Path
Intuition
The minimum number of semesters equals the length of the longest path in the prerequisite graph. This is because courses along the longest dependency chain must be taken sequentially, one per semester.
This approach uses two DFS passes: first to detect cycles (making it impossible to finish), then to find the longest path from any starting node. We use memoization to avoid recomputing path lengths for nodes we have already visited.
Algorithm
- Build an adjacency list from the relations.
- First
dfspass: detect cycles using three states (unvisited, visiting, visited).- If we encounter a node in the "visiting" state, a cycle exists.
- Return
-1if any cycle is found.
- Second
dfspass: compute the longest path starting from each node.- For each node, recursively find the maximum path length through its neighbors.
- Cache results to avoid redundant computation.
- Return the maximum path length across all nodes.
class Solution:
def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
graph = {i: [] for i in range(1, N + 1)}
for start_node, end_node in relations:
graph[start_node].append(end_node)
# check if the graph contains a cycle
visited = {}
def dfs_check_cycle(node: int) -> bool:
# return True if graph has a cycle
if node in visited:
return visited[node]
else:
# mark as visiting
visited[node] = -1
for end_node in graph[node]:
if dfs_check_cycle(end_node):
# we meet a cycle!
return True
# mark as visited
visited[node] = False
return False
# if has cycle, return -1
for node in graph.keys():
if dfs_check_cycle(node):
return -1
# if no cycle, return the longest path
visited_length = {}
def dfs_max_path(node: int) -> int:
# return the longest path (inclusive)
if node in visited_length:
return visited_length[node]
max_length = 1
for end_node in graph[node]:
length = dfs_max_path(end_node)
max_length = max(length+1, max_length)
# store it
visited_length[node] = max_length
return max_length
return max(dfs_max_path(node)for node in graph.keys())Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of
relationsand is the number of courses.
3. Depth-First Search: Combine
Intuition
We can combine cycle detection and longest path computation into a single DFS. The key insight is that a node in the "visiting" state during DFS indicates a cycle. We use -1 as a sentinel value to indicate both "currently visiting" and "cycle detected."
When we finish processing a node, we store its longest path length. If we ever encounter -1 from a recursive call, we propagate that cycle indicator upward. This eliminates the need for a separate cycle detection pass.
Algorithm
- Build an adjacency list from the relations.
- Run
dfsfrom each unvisited node:- Mark the node as visiting (
-1). - Recursively compute the longest path through neighbors.
- If any neighbor returns
-1, propagate the cycle indicator. - Store the computed path length and return it.
- Mark the node as visiting (
- Track the maximum path length across all nodes.
- Return
-1if a cycle was detected, otherwise return the maximum path length.
class Solution:
def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
graph = {i: [] for i in range(1, N + 1)}
for start_node, end_node in relations:
graph[start_node].append(end_node)
visited = {}
def dfs(node: int) -> int:
# return the longest path (inclusive)
if node in visited:
return visited[node]
else:
# mark as visiting
visited[node] = -1
max_length = 1
for end_node in graph[node]:
length = dfs(end_node)
# we meet a cycle!
if length == -1:
return -1
else:
max_length = max(length+1, max_length)
# mark as visited
visited[node] = max_length
return max_length
max_length = -1
for node in graph.keys():
length = dfs(node)
# we meet a cycle!
if length == -1:
return -1
else:
max_length = max(length, max_length)
return max_lengthTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of
relationsand is the number of courses.
Common Pitfalls
Forgetting to Detect Cycles
If the prerequisite graph contains a cycle, it is impossible to complete all courses. Returning the longest path length without first checking for cycles will give a wrong answer. Always verify that all courses can be processed (studied count equals N) before returning the result.
Counting Courses Instead of Semesters in BFS
With Kahn's algorithm, each BFS level represents one semester, not one course. The answer is the number of levels traversed, not the total number of courses processed. Incrementing the counter for each course instead of each level gives an incorrect result.
Using the Wrong DFS State Values
When combining cycle detection with longest path calculation, using -1 as both "visiting" and "cycle detected" requires careful handling. If a node returns -1, you must propagate this upward immediately rather than continuing to compute path lengths.