Elegant Java code (beats 66%)

  • 0

    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++)
            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) {
            for (int coursePreq : coursesPreqs[course]){
                if (greySet.contains(coursePreq)) return false;
                if (blackSet.contains(coursePreq)) continue;
                if (!canFinish(coursePreq, coursesPreqs, greySet, blackSet)) return false;
            return true;

Log in to reply

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