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.
1function findOrder(numCourses, prerequisites) {
2 let inDegree = new Array(numCourses).fill(0);
3 let graph = Array.from({length: numCourses}, () => []);
4
5 for (let [course, prereq] of prerequisites) {
6 graph[prereq].push(course);
7 inDegree[course]++;
8 }
9
10 let queue = [];
11 for (let i = 0; i < numCourses; i++) {
12 if (inDegree[i] === 0) queue.push(i);
13 }
14
15 let order = [];
16 while (queue.length) {
17 const node = queue.shift();
18 order.push(node);
19 for (let neighbor of graph[node]) {
20 inDegree[neighbor]--;
21 if (inDegree[neighbor] === 0) queue.push(neighbor);
22 }
23 }
24
25 return order.length === numCourses ? order : [];
26}
27The code above follows the same logic as the Python solution. It constructs the prerequisite graph and maintains an in-degree array before performing BFS with a queue to determine a valid course order.
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.