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 š
Top comments (0)