Course Schedule

Problem Statement

LeetCode-207: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where $prerequisites[i] = [a_i \space, b_i]$ indicates that you must take course $b_i$ first if you want to take course $a_i$.

Return true if you can finish all courses. Otherwise, return false.

Approach

We will be discussing two approaches to solve this problem:

Dependency Approach (Not Working)

I started with a rather simple approach to solve this question (which did not work for some test cases). My idea was to keep track of the courses that are prerequisites for each course using a HashMap.

On a high level, the algorithm can be described below. A pair of $[course, dependency]$ denotes that course is dependent on dependency):

1. For every pair, check if both the entries are equal and return false if that is the case (cyclic).
2. Else, check if the current dependency is already present in the HashMap. If yes, this means, we have already calculated all the dependencies for this dependency.
   • Get all the dependencies for the current dependency and check if the current course is present in the list of dependencies. If yes, return false as this is a cyclic dependency.
3. Else, get the current dependencies for the current course and add current dependency to it.

Here is a Java implementation of the above approach:

public boolean canFinish(int numCourses, int[][] prerequisites) {
    Map<Integer, Set<Integer>> dep = new HashMap<>();
    
    for(int[] schedule : prerequisites){
        int course = schedule[0];
        int dependency = schedule[1];
        if(course == dependency){
            return false;
        } else if(dep.containsKey(dependency)){
            Set<Integer> vals = dep.get(dependency);
            for(int val : vals){
                if(val == course){
                    return false;
                }
            }
        }
        Set<Integer> vals = dep.getOrDefault(course, new HashSet<>());
        vals.add(dependency);
        dep.put(course, vals);
    }   
    
    return true;
}

As mentioned previously, this approach does not work for all test cases. Consider the following test case:

[[1,0],[0,2],[2,1]]

The above test case will return true using the above approach. However, the correct answer should be false as there is a cyclic dependency. This happens because I was not considering any transitive dependencies and only checking the immediate dependencies present in the HashMap.

For example, in the above test case:

1. In the first iteration, entry 1:{0} is added to the HashMap.
2. Next, as 2 is still not present in the HashMap, entry 0:{2} is also added.
3. When working with next pair i.e. [2,1], we see that 1 is already present in the HashMap and we check if 2 is present in the dependencies of 1. Since 2 is not present, add a new pair 2:{1} to the HashMap and returns true.

But this is where the problem lies as we can see that there is a cyclic dependency in the graph. In this case, during the second iteration, as 0 is already a known dependency for 1, we should also add 2 as a transitive dependency for 1 which would have helped us to identify the cyclic dependency.

From this implementation, we can see that we need to consider the transitive dependencies as well which points towards a graph problem.

Graph Approach

If we consider each course as a node and draw an edge from $b_i \to a_i$​ for any prerequisite $[a_i​ \space, b_i​]$ we get a directed graph. In this case, the problem can be reduced to finding if there is a cycle in the graph.

There are a few of ways to implement cycle detection in a DAG. We will be discussing an extension to Kahn’s Algorithm i.e. Topological Sort approach to solve this problem:

1. Keep track of the in-degree of each node.
2. On the lines of BFS algorithm, add all the nodes with in-degree 0 to the queue.
3. For every node in the queue, reduce the in-degree of all the nodes connected to it by 1.
4. If the in-degree of any node becomes 0, add it to the queue.
5. Repeat the above steps until the queue is empty.

If in the end, the number of nodes visited (removed from queue) is equal to the total number of courses, return true. Else, return false.

Implementation

Here is a Java implementation of the above approach:

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[numCourses];

        // populate the graph with an
        // edge between from and to nodes
        // also populate the indegree of to nodes
        for(int[] dep : prerequisites){
            int from = dep[1];
            int to = dep[0];

            indegree[to]++;
            graph.computeIfAbsent(from, key -> new ArrayList<>()).add(to);
        }

        // let's populate all nodes
        // with in-degree as zero
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i < numCourses; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }

        // BFS from nodes with zero indegree
        int visitedNodes = 0;
        while(!queue.isEmpty()){
            int from = queue.remove();
            visitedNodes++;
            if(graph.containsKey(from)){
                // reduce the indegree for all 
                // of its neighbors
                for(int to : graph.get(from)){
                    indegree[to]--;

                    // if new indegree is zero
                    // add to queue
                    if(indegree[to] == 0){
                        queue.add(to);
                    }
                }
            }
        }
        return visitedNodes == numCourses;
    }

Complexity Analysis

The overall time complexity for this approach is $O(N+M)$ where $N$ is the number of courses (nodes) and $M$ is the size of prerequisites (edges).

Similarly, the space complexity for this approach is also $O(N+M)$ due to:

1. HashMap to represent the graph with $N$ nodes.
2. Queue used to store the nodes with zero indegree. This again can have a maximum of $N$ nodes.
3. indegree array to store the indegree of each node. This array will have $M$ elements.