🏛️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 course0you have to first take course1.
Return true if you can finish all courses. Otherwise, return false.
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.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.
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
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.
Space complexity I am not too confident about the space complexity. The space complexity is O(N + E)
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).
in_degrees : this is a dictionary with V number of keys with a single interger value as value. So this occupies O(V)
queues : this is never be higher than O(V)
Last updated