Topological Sort Solution


  • 0
    W
    boolean classSchedule(int numCourses, int[][] prerequisites) {
        int[] numPrereqs = new int[numCourses];
        for (int[] prereq : prerequisites)
            numPrereqs[prereq[0]]++;
        
        int counter = 0; //for space efficiency: dont need a queue
        Queue<Integer> processNext = new LinkedList<Integer>();
    
        // do courses with no prereqs first
        for(int i = 0; i < numCourses; i++)
            if (numPrereqs[i] == 0) processNext.add(i);
        
        // keep adding courses with no remaining prereqs
        while(!processNext.isEmpty()) {
            int curr = processNext.poll();
            for(int[] prereq : prerequisites) {
                if (prereq[1] == curr) {
                    numPrereqs[prereq[0]]--;
                    if (numPrereqs[prereq[0]] == 0) 
                        processNext.add(prereq[0]);
                }
                counter++;
            }
            if (counter == n) return true;
            else return false;
    }
    

Log in to reply
 

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