DEV Community

codingpineapple
codingpineapple

Posted on

3 2

207. Course Schedule (javascript solution)

Description:

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// Use Kahn's algorithm to see if a topological ordering is possible
// In this problem each item in the prequisites array comes in the form [a,b], were b is the course you need to take first before you can take a
var canFinish = function(numCourses, prerequisites) {
    // Initialize an array that holds the counts of how many times each course was an 'a'
    // which means you needed to take another course before you could take it
    // If imagined as a graph, these courses all have edges going into them from some other vertex and the count represents the total number of edges going into each one
    const inDegree = new Array(numCourses).fill(0);
    // Count how many times each course is an 'a'
    // Each course count will be placed at a corresponding index in the inDegree array
    for(const pre of prerequisites) {
        inDegree[pre[0]]++
    }
    // Initialize array of courses that have no prerequisites, these will always be in the 'b' position of the [a,b] group
    // If imagined as a graph, these courses will have no edges pointing into them
    const zeroDegree = [];
    // If no prerequisites were found for a course it's count will be 0
    // Add these to the zeroDegree array 
    for(let i = 0; i < numCourses; i++) {
        if(inDegree[i]===0) {
            zeroDegree.push(i);
        }
    }
    // If the zeroDegree array is empty, that means there is no heirarchical relation because you cannot not take a single course without needing to take another one first
    if(zeroDegree.length === 0) return false;

    // Loop through the zeroDegree array
    while(zeroDegree.length) {
        // Remove a course from the array on every iteration
        const course = zeroDegree.pop();
        // Account for all the times in the prerequisites array that this course was a precourse to another course, i.e. course was in the 'b' position
        for(const pre of prerequisites) {
            if(course === pre[1]) {
                // Subtract from the count of the 'a' course matched
                inDegree[pre[0]]--
                // If the 'a' course in this relationship is 0 in the inDegree array, that means we have accounted for all the times it was used
                // If imagined as a graph, we have accounted for all edges leading into this vertex
                if(inDegree[pre[0]]===0) {
                    // Push this course into the zeroDegree and see if it is needed as a precourse for any other courses
                    // If imagined as a graph, see if this vertex has an edge that points into another vertix
                    zeroDegree.push(pre[0])
                }
            }
        }
    }
    // If there is any index in the array that is not 0, that means there is a precourse relationship that is unaccounted for
    for(const num of inDegree) {
        if(num!== 0) return false
    }
    return true;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

👋 Kindness is contagious

Engage with a wealth of insights in this thoughtful article, cherished by the supportive DEV Community. Coders of every background are encouraged to bring their perspectives and bolster our collective wisdom.

A sincere “thank you” often brightens someone’s day—share yours in the comments below!

On DEV, the act of sharing knowledge eases our journey and forges stronger community ties. Found value in this? A quick thank-you to the author can make a world of difference.

Okay