210. Course Schedule II

Description

There are a total of n courses you have to take labelled from 0 to n - 1.

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
All the pairs [ai, bi] are distinct.

Approach

Examples

Input: numCourses = 2, prerequisites = [[1, 0]]

Output: [0, 1]

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0, 1].

Solutions

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
        int[] result = new int[numCourses];
        
        if(prerequisites.length == 0) {
            for(int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        
        int[] prereqCounter = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++) {
            prereqCounter[prerequisites[i][0]]++;
        }
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++) {
            if(prereqCounter[i] == 0) queue.add(i);
        }
        
        int noPrereqCourses = queue.size();
        int j = 0;
        
        while(!queue.isEmpty()) {
            int course = queue.remove();
            result[j++] = course;
            
            for(int i = 0; i < prerequisites.length; i++) {
                if(prerequisites[i][1] == course) {
                    prereqCounter[prerequisites[i][0]]--;
                    if(prereqCounter[prerequisites[i][0]] == 0) {
                        queue.add(prerequisites[i][0]);
                        noPrereqCourses++;
                    }
                }
            }
        }
        
        if(noPrereqCourses == numCourses) {
            return result;
        }
        
        return new int[0];
    }
}

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int index = 0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
        int[] result = new int[numCourses];
        
        if(prerequisites.length == 0) {
            for(int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        
        ArrayList[] courses = new ArrayList[numCourses];
        for(int i = 0; i < numCourses; i++) {
            courses[i] = new ArrayList<Integer>();
        }
        
        for(int[] pre: prerequisites) {
            courses[pre[0]].add(pre[1]);
        }
        
        int[] processedStatus = new int[numCourses];
        
        for(int i = 0; i < numCourses; i++) {
            if(processedStatus[i] == 0) {
                if(isCycleExist(i, courses, processedStatus, result)) {
                    return new int[0];
                }
            }
        }
        
        return result;
    }
    
        private boolean isCycleExist(int u,
                                 ArrayList[] courses, 
                                 int[] processedStatus,
                                 int[] orderedCourses) {
        if(processedStatus[u] == 2) return true;
                
        processedStatus[u] = 2;
        
        ArrayList<Integer> course = courses[u];
        for(int v = 0; v < course.size(); v++) {
            if(processedStatus[course.get(v)] != 1) {
                if(isCycleExist((int)course.get(v), courses, processedStatus, orderedCourses)) {
                    return true;
                }
            }
        }
        
        processedStatus[u] = 1;
        orderedCourses[index++] = u;
        
        return false;
    }
}

Follow up

Previous209. Minimum Size Subarray Sum Next211. Design Add and Search Words Data Structure

Last updated 5 years ago

Was this helpful?