Course Schedule

Patrick Leaton
Published: June 29, 2021, 6:31 p.m.
Problem Description

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

  • 1 <= numCourses <= 10^5
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

 

The description was taken from https://leetcode.com/problems/course-schedule/.

Problem Solution

#O(C+P) Time, O(C+P) Space
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        prereq_map = {}
        seen = {}
 
        for course in range(0, numCourses):
            prereq_map[course] = []
            seen[course] = False
       
        for course, prereq in prerequisites:
            prereq_map[course].append(prereq)
           
        def dfs(course:int) -> bool:
            if seen[course]:
                return False
 
            if not prereq_map[course]:
                return True
 
            seen[course] = True
 
            for prereq in prereq_map[course]:
                if not dfs(prereq):
                    return False
 
            seen[course] = False
            prereq_map[course] = []
            return True
   
        for course in range(0, numCourses):
            if not dfs(course):
                return False
        return True

Problem Explanation

To figure out if we can complete the prerequisites for each course, we will need to get the relationships between each course and each prerequisite course that needs to be taken grouped together.

Without physically creating a graph by instantiating nodes using the input matrix, we can use an adjacency list to map each prerequisite to each course.  

We can then solve this problem by performing a Depth-First Search on the number of courses that are input, go through their prerequisites and check off the ones we are able to take.  If there are no cycles, meaning there aren't two classes that are prerequisites of each other then we should be able to take each course.  

Let's start up by creating our adjacency list, prereq_map, and our seen dictionary to track cycles.

        prereq_map = {}
        seen = {}

 

We will then go through the number of courses we have to initialize an empty prerequisite array within our adjacency list, and also add them to our seen dictionary with the initial value of false since we haven't seen them yet.

        for course in range(0, numCourses):
            prereq_map[course] = []
            seen[course] = False

 

Next, we will go through each course and prerequisite given from the input prerequisites list and append each prerequisite to each course within our adjacency list.

        for course, prereq in prerequisites:
            prereq_map[course].append(prereq)

Now we will build our recursive, dfs function.

It will take as arguments, a course integer and it will return a boolean value for which the prerequisites can be satisfied for the course without cycles.

        def dfs(course:int) -> bool:

 

Being a recursive function, we need to ensure the base cases aren't met before performing a DFS on the given course.

If the course has been seen in the current DFS path, then that means the course this given prerequisite is for requires the initial course to also be taken as a prerequisite.  Unless we try to bribe the dean of our college, we aren't going to be able to take the given courses so we will return false.

            if seen[course]:
                return False

 

Also, if our current course has no prerequisites, then there is nothing to do a DFS on, so we can return from here also.

            if not prereq_map[course]:
                return True

 

If neither of these base cases is met, we will perform our DFS.

We'll breadcrumb our path by adding our current course to the seen dictionary.

            seen[course] = True

 

Then, for each prerequisite mapped to the course within the adjacency list, we will see if their prerequisites can be satisfied.  If at least one of them cannot be, then we should break from the loop early and return false because we would be wasting time investigating the remaining prerequisites.

            for prereq in prereq_map[course]:
                if not dfs(prereq):
                    return False

 

If the prerequisites for the given function call's course can be satisfied, then we will remove our breadcrumb, wipe our prerequisite array clean, and let our recursive parent call know that the DFS is good from here.

            seen[course] = False
            prereq_map[course] = []
            return True

Now, all there is left to do is make the initial calls.  

We will iterate through each course number and run a DFS on it.  The reason why we can't just run a DFS on one course and assume it will recursively run on every other course is that some courses may not have prerequisites nor are they prerequisites to others.  In that case, it would be disconnected from the graph and wouldn't be searched.

If all of the courses return true from each path of their DFS, all courses can be taken.

        for course in range(0, numCourses):
            if not dfs(course):
                return False
        return True