Leetcode – 207. Course Schedule

This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu

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

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

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)

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 
    }

Finally

    for(let key in preReqMap){
        if(!dfs(key)){
            return false
        }
    }
    return true

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

This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu