Leetcode 207. Course Schedule

Problem

Leetcode 207 - Course Schedule

Example:

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.

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.

Approach

We can create a hash map for each course and its pre requisite courses. We can then run dfs and if the visited course is in it we can return False

Here is the Python code for the solution:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        prereq = {i: [] for i in range(numCourses)}

        for course, req in prerequisites:
            prereq[course].append(req)
        
        visited = set()

        def dfs(c):
            if c in visited:
                return False
            if prereq[c] == []:
                return True

            visited.add(c) 
            for course in prereq[c]:
                if not dfs(course):
                    return False
            
            visited.remove(c)
            prereq[c] = []            
            return True
            

        for c in range(numCourses):
            if not dfs(c):
                return False
        return True

Time Complexity and Space Complexity

Time Complexity: $O(V+E)$

Space Complexity: $O(V+E)$