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

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 😇