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);

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);
}
}

// 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);
}
}
}

// 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];
int pre = prerequisites[i];
}

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;
}

// 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 , last updated on .

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