Course Schedule is one of the most famous interview questions of all time. The idea of this question is based on topological sorting (click here for reference) where you typically use BFS algorithm to solve this kind of question.

Without further ado, let's get into it!

---

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

NOTE: there are a total of n courses you have to take, which are labelled from 0 to n - 1.

The course with prerequisites is denoted in pairs, for example, [1,0] means that you have to first take course 0 before you can take course 1.

The solution can be broken into these few parts:

1. get the course map
2. get the indegree map
3. add course without prerequisites into queue and array
4. decrease indegree level of neighbor course after removing the current course from queue
5. check if the array size is the same as numCourses

Here's the solution for reference:

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        if(numCourses == 0 || prerequisites.length == 0){
            return true;
        }
        
        // 1. we need to find out the course map (course with prerequisites)
        Map<Integer, List<Integer>> courseMap = getCourseMap(numCourses, prerequisites);
        
        // 2. get indegree for each course
        Map<Integer, Integer> indegreeMap = getIndegreeMap(numCourses, courseMap);
             
        Queue<Integer> queue = new LinkedList<>();     
        List<Integer> result = new ArrayList<>();
        
        // 3. add the course without prerequisites into queue
        for(int i = 0 ; i < numCourses; i++){
            if(!indegreeMap.containsKey(i)){
                queue.offer(i);
                result.add(i);
            }            
        }
        
        // 4. decrease the indgree level of the neighbor course after removing the current course from queue
        // add the course with 0 indegree to queue and array
        
        while(!queue.isEmpty()){ 
            Integer course = queue.poll();
            for(Integer neighbor : courseMap.get(course)){
                indegreeMap.put(neighbor, indegreeMap.get(neighbor) - 1);    
                if(indegreeMap.get(neighbor) == 0){
                    queue.offer(neighbor);
                    result.add(neighbor);
                }
            }
        }
        
        // 5. check if the course-ordered array's size is same as the numCourses
        return result.size() == numCourses;
    }
    
    
    private Map<Integer, List<Integer>> getCourseMap(int numCourses, int [][] prerequisites){
        
        Map<Integer, List<Integer>> courseMap = new HashMap<>();
        
        // 1. initialize the map
        for(int i = 0; i < numCourses; i++){
            courseMap.put(i, new ArrayList<>()); 
        }
        
        // 2. add current course to the prerequisite course
        for(int i = 0; i < prerequisites.length; i++){
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            courseMap.get(pre).add(cur);            
        }
        
        return courseMap;
        
    }
    
    private Map<Integer, Integer> getIndegreeMap(int numCourses, Map<Integer, List<Integer>> courseMap){
        
        Map<Integer, Integer> indegreeMap = new HashMap<>();

        for(int i = 0 ; i < numCourses; i++){   
            for(Integer neighbor : courseMap.get(i)){
                if(indegreeMap.containsKey(neighbor)){
                    indegreeMap.put(neighbor, indegreeMap.get(neighbor) + 1);
                } else{
                    indegreeMap.put(neighbor, 1);
                }
            }
        }
        
        return indegreeMap;
    }

As you may have noticed, the BFS method are very similar. You can call it a template or anything you want, the idea is to get the indegree of each node and add the node with 0 indegree (usually) into queue, then keep removing current node and adding new nodes (depends on the case scenario) until the queue is empty. Lastly, check if the result is what we intended for.

---

Follow up: can you return the ordering of courses you should take to finish all courses?

NOTE: if there are multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array will do.

In this follow-up question, you just need to make sure that you return an empty array if the courses cannot be completed, otherwise return the result array.

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
        ...
        
        // 5. return empty array if courses cannot be completed
        if(result.size() != numCourses){
            return new int[0];
        }
        
        // 6. convert ArrayList into integer array
        int [] resultArr = new int[result.size()];
        for(int i = 0; i < result.size(); i++){ 
            resultArr[i] = result.get(i);
        }
        
        return resultArr;
    }

---

I hope this have been helpful. More BFS questions coming right up. Thanks for reading!

Post was published on 25 Jan 2020, last updated on 25 Jan 2020.

Like the content? Support the author by paypal.me!