Help with optimizing this code!


  • 0
    Z

    Help with optimizing this code. It's a simple DFS but exceeds time limit in 36th test case out of 37. Is the order of this test case O(E)?

    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            if(prerequisites == null || prerequisites.length ==0) return true;
            Map<Integer, List<Integer>> preByCourse = new HashMap<>();
            for(int[] pre : prerequisites){
                int course = pre[0];
                int req = pre[1];
                if(!preByCourse.containsKey(course)){
                    preByCourse.put(course, new ArrayList<>());
                }
                preByCourse.get(course).add(req);
                
            }
            
            Set<Integer> visited = new HashSet<>();
            for(Integer course : preByCourse.keySet()){
                boolean possible = visit(course, visited, new HashSet<>(), preByCourse);
                if(!possible){
                    return false;
                }
            }
            
            return true; 
            
        }
        
        public boolean visit(Integer course, Set<Integer> visited, Set<Integer> localVisited, Map<Integer, List<Integer>> preByCourse){
            if(visited.contains(course)){
                return true;
            }
            
            if(localVisited.contains(course)){
                return false;
            }
            
            Set<Integer> lVisited =new HashSet<>(localVisited);
            lVisited.add(course);
            
             if(!preByCourse.containsKey(course)){
                 visited.add(course);
                 return true;
             }
            boolean possible = true;
            for(Integer prereq : preByCourse.get(course)){
                possible &= visit(prereq, visited, lVisited, preByCourse);
            }
            
            visited.add(course);
            return possible;
        }
    }
    

Log in to reply
 

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