Leetcode - 207. Course Schedule
Published: 2024-06-24 03:53:58

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bcmml8h90z6o1lei5028.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gbc9jx1igta2q2myn512.png)

This code gives the adjacency list or like a tree 
```javascript
 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)
```



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/duy5ljul4puii0ko78dk.png)

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

```javascript
    //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

```javascript
    for(let key in preReqMap){
        if(!dfs(key)){
            return false
        }
    }
    return true
```
Refer to - [this video by neetcode](https://www.youtube.com/watch?v=EgI5nU9etnU&t=249s) if you are not able to understand the code

Please do follow the series if you are struggling with leetcode questions 😇