JavaScript solution - DFS and backtracking


  • 0
    D
    /**
     * @param {number} numCourses
     * @param {number[][]} prerequisites
     * @return {boolean}
     */
    var canFinish = function(numCourses, prerequisites) {
        
        if(prerequisites.length == 0){
            return true;
        }
        
        let visitedHash = {};
        let adjHash = {};
        let isCycle = false;
        
        // get all the dependencies as adj list
        for(let i = 0; i < prerequisites.length; i++){
            if(!adjHash[prerequisites[i][0]]){
                adjHash[prerequisites[i][0]] = [];
            }
            adjHash[prerequisites[i][0]].push(prerequisites[i][1]);  
        }
        
        
        let stack = [];
        for(let key in adjHash){
            
            visitedHash = {};
    
            visitedHash[key] = true;
            stack.push(key);
        
            dfs();
    
        }
        
        function dfs(){
            let pop = stack.pop();
            
            // cycle is found.. no need to proceed.. we cannot complete all courses
            if(isCycle){
                return;
            }
            
            // there is no prerequisite for this course.. we are good
            let adj = adjHash[pop];
            if(adj == undefined){
                return;
            }
            
            
            // for each prerequisite.. check if cycle is present
            // if yes, then we cannot complete all courses
            for(let i = 0; i < adj.length; i++){
                
                // if we have visited the node previously in this round for the current course...
                // we cannot complete all courses..
                // this visitedHash is reset for each round of new course that we check
                if(visitedHash[adj[i]]){
                    isCycle = true;
                    return;
                }
                
                if(adjHash[adj[i]]){
                    visitedHash[adj[i]] = true;
                }
                
                stack.push(adj[i]);
                dfs(adj[i]);
                
                // backtrack
                visitedHash[adj[i]] = false;
            }
        
        }
        
        return !isCycle;
        
        
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.