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 😇

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up