Course Schedule II

Patrick Leaton
Published: July 22, 2021, 6:19 p.m.
Problem Description

There are a total of n courses you have to take labelled from 0 to n - 1.

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

 

Example 1:

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

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

 

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.

 

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

Problem Solution

#O(N+E) Time, O(N+E) Space
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        seen, course_order, prereq_map = {}, {}, {}
       
        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 course in course_order:
                return True
 
            seen[course] = True
            for prereq in prereq_map[course]:
                if not dfs(prereq):
                    return False
 
            seen[course] = False
            prereq_map[course] = []
            course_order[course] = True
            return True
       
        for course in range(0, numCourses):
            if not dfs(course):
                return []               
        return course_order.keys()

 

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.  

The only difference between this version of the question and the previous one is we will keep a course order HashMap that we will add each course to after the DFS of their prerequisite courses ends.  By doing this, we will be able to first get the courses that are leaves at the bottom of the recursive tree, which would be the courses that have no prerequisites, then, get the courses that the leaves were prerequisites for, and so on. 

This is the same idea as a postorder traversal on a binary tree.

Let's start up by creating our adjacency list, prereq_map, our course_order hashmap that we will add each course to at the end of their DFS, and our seen dictionary to track cycles.

        seen, course_order, prereq_map = {}, {}, {}

 

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 recursive tree, 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 the course is already in the course_order dictionary, we already said to take this course so we don't need to do any more work here.

            if course in course_order:
                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, add the course to the course_order dictionary, and let our recursive parent call know that the DFS is good from here.

            seen[course] = False
            prereq_map[course] = []
            course_order[course] = True
            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, and we will return the course_order keys which will keep the order of when the courses were added from the DFS.

        for course in range(0, numCourses):
            if not dfs(course):
                return []               
        return course_order.keys()