My Java solution


  • 0
    Q

    Just a minor modification to Course Schedule 1 solution

    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Map<Integer, List<Integer>> courseToPrereqs = new HashMap<Integer, List<Integer>>();
            for (int i=0;i<prerequisites.length;i++){
                int courseId = prerequisites[i][0];
                int prereqId = prerequisites[i][1];
                
                List<Integer> prereqs = courseToPrereqs.get(courseId);
                if (prereqs == null){
                	prereqs = new ArrayList<Integer>();
                	courseToPrereqs.put(courseId, prereqs);
                }
                prereqs.add(prereqId);
            }
            boolean[] cycleDetector = new boolean[numCourses];
            boolean[] visitedEarlier = new boolean[numCourses];
            List<Integer> classes = new ArrayList<Integer>();
            boolean[] classesChecker = new boolean[numCourses];
            for (int i=0;i<numCourses;i++){
            	if (!validate(cycleDetector, i, courseToPrereqs, visitedEarlier, classes,classesChecker)){
                	return new int[]{};
                }            
            }
            for (int i=0;i<numCourses;i++){
            	if (!(classes.contains(i))){
            		classes.add(i);
            	}
            }
            int[] array = new int[classes.size()];
            for (int i=0;i<classes.size();i++){
            	array[i]=classes.get(i);
            }
            return array;
        }
        private boolean validate(boolean[] cycleDetector, int course, Map<Integer, 
            List<Integer>> courseToPrereqs,  boolean[] visitedEarlier, List<Integer> classes,
             boolean[] classesChecker){
            if (visitedEarlier[course]){ 
                return true;
            }
        	if (cycleDetector[course]){
        		return false;
        	}
        	List<Integer> prereqs = courseToPrereqs.get(course);
        	
        	cycleDetector[course] = true;
        	if (prereqs != null){
            	for (int prereq:prereqs){
            		if (!validate(cycleDetector, prereq, courseToPrereqs, visitedEarlier, classes,
            		    classesChecker)){
            			return false;
            		}
            		if (classesChecker[prereq] == false){
            			classes.add(prereq);
            			classesChecker[prereq] = true;
            		}
            	}
        	}
        	else{
        		if (classesChecker[course] == false){
        			classes.add(course);
        			classesChecker[course] = true;
        		}
        	}
        	visitedEarlier[course] = true;
        	return true;
        }
    }

Log in to reply
 

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