DEV Community

Cover image for Leetcode - 207. Course Schedule
Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on β€’ Edited on

Leetcode - 207. Course Schedule

U can read the question properly and give a try once before coming to the solution

Incase you have tried and need help you can continue through the solution πŸ€—

Taking the *Example - 1 *
Input: numCourses = 2, prerequisites = [[1,0]]
so this tells us that we need to be completing 2 courses
and in order to complete course 1 we need to complete course 0
so this is possible as u can first complete course0 and then course 1

Taking the Example - 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
so here we want to complete the 2 courses course 1 and course 0 , and the prerequisites tell us that

prerequisite1 -> [1,0] in order to complete course 1 i need to complete course 0 ,

but the catch is to complete course 0. i need to complete course 1 , did u observe the loop here

Image description

so u can never complete the 2 courses so we need to return false

Now the problem is u might have got this but u didn't get how to put this idea in code form πŸ˜–

idea -> if a loop is found we return false otherwise true
to find if we have a loop we need to traverse the tree and see if we r visiting any node twice on exploration

we can explore the tree by graph traversal algorithms like DFS (Depth First Search) or BFS (Breadth First Search) . In this blog we are going with DFS

DFS is like we visit all the neighbour's of a node and move to the next node .

so in-order to traverse the tree , we need to have the tree 🌴.

Example 3

Image description

This code gives the adjacency list or like a tree

 const prerequisites = [[0,1],[0,2],[1,3],[1,4],[3,4]]
 const preReqMap = {};
    prerequisites.forEach((item)=>{
        if(preReqMap.hasOwnProperty(item[0])){
            preReqMap[item[0]] =  [...preReqMap[item[0]] ,item[1]]
        }else{
            preReqMap[item[0]] = [item[1]]
        }
    })

console.log(preReqMap)
Enter fullscreen mode Exit fullscreen mode

Image description

u now know which node is connected to which all neighbors now we need to traverse and while traversing if we found loop we return false

    //visitset storing which all we have visited
    let visited = {}
    const dfs = (node) =>{
        if(visited[node]){
            return false // if we have already visited it 
        }
    if(preReqMap[node] !==undefined){
        if(preReqMap[node].length == 0){
            return true //if no neighbour's that means course can be completed as no prerequisite is needed
        }
        visited[node] = true;//marking it visited

     //Exploring all neighbors of the node in recursive fashion
        for(let val of preReqMap[node]){
                if(!dfs(val)){
                    return false // retur
                }
        }

    } 
        visited[node] = false;    
        preReqMap[node] = [];   
        return true 
    }

Enter fullscreen mode Exit fullscreen mode

Finally

    for(let key in preReqMap){
        if(!dfs(key)){
            return false
        }
    }
    return true
Enter fullscreen mode Exit fullscreen mode

Refer to - this video by neetcode if you are not able to understand the code

Please do follow the series if you are struggling with leetcode questions πŸ˜‡

Sentry image

See why 4M developers consider Sentry, β€œnot bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more