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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] FindOrder(int numCourses, int[][] prerequisites) {
List<int>[] graph = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) graph[i] = new List<int>();
foreach (var prereq in prerequisites) graph[prereq[1]].Add(prereq[0]);
bool[] visited = new bool[numCourses];
bool[] recStack = new bool[numCourses];
List<int> order = new List<int>();
for (int i = 0; i < numCourses; i++) {
if (HasCycle(graph, visited, recStack, i, order))
return new int[0];
}
order.Reverse();
return order.ToArray();
}
private bool HasCycle(List<int>[] graph, bool[] visited,
bool[] recStack, int node, List<int> order) {
if (recStack[node]) return true;
if (visited[node]) return false;
visited[node] = true;
recStack[node] = true;
foreach (int neighbor in graph[node])
if (HasCycle(graph, visited, recStack, neighbor, order))
return true;
recStack[node] = false;
order.Add(node);
return false;
}
}
The C# solution leverages DFS to topologically sort the courses while simultaneously checking for cycles. The recursion stack helps identify cycles, while completed nodes are added to a list in post-order to establish the course sequence.