210. Course Schedule II (javascript solution)

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;
};