Description:
There are a total of n courses you have to take labelled from 0 to n - 1.
Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.
Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.
If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Solution:
See my solution to 207 Course Schedule I for more details on how the algorithm uses topological ordering: https://dev.to/cod3pineapple/207-course-schedule-javascript-solution-24e5
Time Complexity : O(n)
Space Complexity: O(n)
var findOrder = function(numCourses, prerequisites) {
// Initialize result array
const result = new Array(numCourses).fill(0)
const inDegree = new Array(numCourses).fill(0);
for(const pre of prerequisites) {
inDegree[pre[0]]++
}
const zeroDegree = [];
for(let i = 0; i < numCourses; i++) {
if(inDegree[i]===0) {
zeroDegree.push(i);
}
}
// Topological sort not possible
if(zeroDegree.length === 0) return []
let i = 0
while(zeroDegree.length) {
const course = zeroDegree.pop()
// Add course to the result array
result[i++] = course
for(const pre of prerequisites) {
if(course === pre[1]) {
inDegree[pre[0]]--
if(inDegree[pre[0]]===0) {
zeroDegree.push(pre[0])
}
}
}
}
// Topological sort not possible
for(const num of inDegree) {
if(num!== 0) return []
}
return result;
};
Top comments (0)