Solution: Course Schedule

Statement#

There are a total of num_courses courses you have to take. The courses are labeled from 0 to num_courses - 1. You are also given a prerequisites array, where prerequisites[i] = [a[i], b[i]] indicates that you must take course b[i] first if you want to take the course a[i]. For example, the pair $[1, 0]$ indicates that to take course $1$, you have to first take course $0$.

Return TRUE if all of the courses can be finished. Otherwise, return FALSE.

Constraints:

• $1 \leq$ num_courses $\leq 1500$
• $0 \leq$ prerequisites.length $\leq 1000$
• prerequisites[i].length $= 2$
• $0 \leq$ a[i], b[i] $<$ num_courses
• All the pairs prerequisites[i] are unique.

Solution#

Initialize the hash map with the vertices and their children. We’ll use another hash map to keep track of the number of in-degrees of each vertex. Then we’ll find the source vertex (with $0$ in-degree) and increment the counter. Retrieve the source node’s children and add them to the queue. Decrement the in-degrees of the retrieved children. We’ll check whether the in-degree of the child vertex becomes equal to zero, and we increment the counter. Repeat the process until the queue is empty.

Note: The in-degree is the number of edges coming into a vertex in a directed graph.

The primary purpose of finding a vertex with 0 in-degree is to find a course with a pre-requisite count of 0. When we take a course, say a (that is the pre-requisite of another course, say b), we’ll decrement the in-degree of b by 1, and if the in-degree count becomes 0, we can say that the b’s pre-requisites have been completed.

The slide deck below illustrates the algorithm above, where num_courses = 6:

Time complexity#

In the algorithm above, each course will become a source only once, and each edge will be accessed and removed once. Therefore, the above algorithm’s time complexity will be $O(V+E)$, where $V$ is the total number of vertices and $E$ is the total number of edges in the graph.

Space complexity#

The space complexity will be $O(V+E)$ because we’re storing all of the edges for each vertex in an adjacency list.

Alternative solution#

To determine if we can finish all courses, we can also use Depth-First Search (DFS) algorithm. We can represent the courses and their prerequisites using a directed graph. Each course will be a node in the graph, and an edge from node A to node B indicates that course B is a prerequisite for course A. Starting from each course, we perform a DFS traversal to explore its dependencies. During the traversal, we mark the current course as being visited. For each dependency of the current course, we recursively perform DFS. If we encounter a course that has already been visited (indicating a cycle), we return False, as it means that there is a circular dependency among the courses, and we cannot complete all the courses. If the DFS traversal completes for a course without encountering any cycles, we mark the course as finished and continue checking the remaining courses. If the DFS traversal is successful for all courses, it means we can complete all the courses, and we return True.

The time and space complexity of this solution is the same as the solution above.