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

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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].

Example 2

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

Output: [0, 2, 1, 3]

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0, 1, 2, 3]. Another correct ordering is [0, 2, 1, 3].

Example 3

Input: numCourses = 1, prerequisites = []

Output: [0]

Solutions

Solution 1

/**
 * 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];
    }
}

Solution 2

/**
 * 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