Sponsored
Sponsored
Consider courses as nodes in a directed graph, and prerequisites as directed edges. We can apply Kahn's algorithm for topological sorting to find the order of courses to take. The algorithm works by using an in-degree array that tracks the number of prerequisites for each course. Courses with zero in-degrees can be taken immediately. As our course order is populated, we decrement the in-degree of their dependent courses, allowing them to be taken in subsequent steps.
Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph and the in-degree array.
1from collections import deque, defaultdict
2
3def findOrder(numCourses, prerequisites):
4 in_degree = [0] * numCourses
5 graph = defaultdict(list)
6
7 for course, prereq in prerequisites:
8 graph[prereq].append(course)
9 in_degree[course] += 1
10
11 queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
12 order = []
13
14 while queue:
15 node = queue.popleft()
16 order.append(node)
17 for neighbor in graph[node]:
18 in_degree[neighbor] -= 1
19 if in_degree[neighbor] == 0:
20 queue.append(neighbor)
21
22 return order if len(order) == numCourses else []
23This solution uses a breadth-first search (BFS) starting from courses with zero prerequisites. As courses are completed, they are removed from their neighbors' prerequisites, enabling further courses to be completed in order. This ensures the result represents a valid topological sort of the course schedule.
Similar to the Kahn's algorithm approach, but using a depth-first search (DFS) to detect cycles and determine the order of courses. In this method, courses are visited, and if a course is revisited while still in the recursion stack, it indicates a cycle, making course completion impossible. The order is determined by recording the exit point of each node during the DFS.
Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph structure and visited array.
1import java.util.ArrayList;
2
The Java solution implements DFS to perform topological sorting while checking for cycles in the graph. During the recursive traversal, we maintain a recursion stack to detect back-edges, alerting us to any cycles in the graph.