Elegant Java code (beats 66%)


  • 0
    L

    The idea is to keep a greyset of currently visiting. If you visit a node in the greyset there is a cycle. We also have a blackset that keeps track of nodes that have been visited, so we don't recompute work.

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<Integer>[] coursesPreqs = new ArrayList[numCourses];
            for (int i = 0; i < coursesPreqs.length; i++) coursesPreqs[i] = new ArrayList<>();
            for (int i = 0; i < prerequisites.length; i++)
                coursesPreqs[prerequisites[i][0]].add(prerequisites[i][1]);
            Set<Integer> greySet = new HashSet<>(); //currently visiting
            Set<Integer> blackSet = new HashSet<>(); //visited
            for (int i = 0; i < numCourses; i++)
                if (!canFinish(i, coursesPreqs, greySet, blackSet)) return false;
            return true;
        }
        
        public boolean canFinish(int course, List<Integer>[] coursesPreqs, Set<Integer> greySet, Set<Integer> blackSet) {
            greySet.add(course);
            for (int coursePreq : coursesPreqs[course]){
                if (greySet.contains(coursePreq)) return false;
                if (blackSet.contains(coursePreq)) continue;
                if (!canFinish(coursePreq, coursesPreqs, greySet, blackSet)) return false;
            }
            greySet.remove(course);
            blackSet.add(course);
            return true;
        }
    

Log in to reply
 

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