🏛️207. Course Schedule

Medium | Grind 75 | Saturday July 9th

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

Let's take an example with the following input: numCourses = 5, prerequisites = [[3,1], [3,2], [1,4], [2,4]]. This basically maps to the diagram below. In order to take course 3, you need course 1 and course 2. However, in order to take course 1 and course 2, you need to take course 4. You can take course 4 because there is no prerequisite for course 4.

case where courses can be completed

case where courses cannot be completed

One major pattern that jumps right out is that formation of cycles when you cannot complete the courses. Therefore, we will try to determine if a cycle exist. If it does, then we know we cannot complete the courses. Otherwise, we can complete the courses.

ALGORITHM

Before doing anything, we will build a dictionary(we will call this DICT_COUNT) containing each vertex and their corresponding number of incoming edges. Then, for the actual algorithm, we will start with the vertex that has 0 incoming edge. If there is no vertex with 0 incoming edges, we know that it is a cycle. In that case, we can just return False. In case there is a vertex with incoming edge 0, we start there. We will build a queue with all the vertext that has 0 incoming edge. Once we have that queue, we will pop the first item and get its neighbors. When we have the neighbors, we will decrement the incoming edge value by 1 for each of the neighbors. If the incoming edge is 0 for any of the neighbor, we add it to the queue. We repeat this until our queue is empty. Once loop is completed (queue is empty), we now loop through the dictionary(DICT_COUNT) that contains the count of incoming edges for each vertext. if we find that there is any vertex that has 1 or more incoming edge, then we know, there is a cycle and we return False. Otherwise, if all the elements in the dictionary(DICT_COUNT) has value 0, then we know we visited every vertext in our previous loop. We then return True.

class Solution:
    def check_schedule(self, in_degrees, graph, queue):
        """ 
           check whether you can complete the courses or not.
           parameter:
                1. in_degrees: dictioonary of number of prerequisites courses 
                    needed for each class
                2. graph: dictionary of courses and ntheir prerequisite courses
                3. queue: list of courses that you can complete. 
           return: 
                bool: whether you can complete courses or not
        """
        while len(queue) != 0: 
            item = queue.pop(0)
            if item in graph:
                neighbors = graph[item]
                for neighbor in neighbors: 
                    in_degrees[neighbor] -= 1
                    if in_degrees[neighbor] == 0: 
                        queue.append(neighbor)
        
        for key, value in in_degrees.items(): 
            if value != 0: 
                return False
            
        return True
        
    
    def make_queue(self, in_degrees):
        """ 
            make a list of courses without any prerequisite.
            parameter:
                1. in_degrees: dictioonary of number of prerequisites courses
                    needed for each class
            return: 
                list: list of classes without preerequisite
        """
        
        queue = []  
        for key,value in in_degrees.items(): 
            if value == 0: 
                queue.append(key)
        return queue
    
        
    def make_graph(self, prerequisites):
        """ 
           convert the input array into dictionary to mimic a graph and count 
           the pre-reqs needed for each course. 
           parameter:
                1. prerequisites: array of courses and their prerequisites
           return: 
                1. graph: dictionary format of cour courses and their pre-reqs
                2. in_degrees: dictionary of number of pre-reqs needed for each
                    class
        """
        
        graph = {}
        in_degrees = {}
        for item in prerequisites: 
            # convert to graph
            if item[0] in graph: 
                graph[item[0]] += [item[1]]
            else: 
                graph[item[0]] = [item[1]]

            # count incoming edges
            if item[1] in in_degrees: 
                in_degrees[item[1]] += 1    
            else: 
                in_degrees[item[1]] = 1

            #case where vertext has no incoming edges
            if item[0] not in in_degrees: 
                in_degrees[item[0]] = 0
                
        return graph, in_degrees
    
    
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if not prerequisites: return True #if the prerequisite array is empty

        graph, in_degrees = self.make_graph(prerequisites)
        queue = self.make_queue(in_degrees)
        
        print(graph, in_degrees)
        return self.check_schedule(in_degrees, graph, queue)
    
    

TIME AND SPACE COMPLEXITY

1. Time complexity

   we have to visit every vertext once. When we are at the vertex, we then visit every edge. Therefore the time compexity is O(V + E) where V is number of vertex and E is number of edges.

2. Space complexity I am not too confident about the space complexity. The space complexity is O(N + E)

   1. graph: this is a dictionary with V keys and each V with its correspnding neighbors. The total number of neighbors is equal to edges. Otherway to look at is the neighbors are basically the edges. O(V + E).

   2. in_degrees : this is a dictionary with V number of keys with a single interger value as value. So this occupies O(V)

   3. queues : this is never be higher than O(V)