Solution: Course Schedule

Let's solve the Course Schedule problem using the Topological Sort pattern.

Statement

There are a total of numCourses courses you have to take. The courses are labeled from 0 to numCourses - 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][1, 0] indicates that to take course 11, you have to first take course 00.

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

Constraints:

  • 1≤1 \leq numCourses ≤2000\leq 2000
  • 0≤0 \leq prerequisites.length ≤5000\leq 5000
  • prerequisites[i].length =2= 2
  • 0≤0 \leq a[i], b[i] << numCourses
  • 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 00 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’ll 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 numCourses = 6:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.