0207-course-schedule

Try it on leetcode

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 <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Solution(Python)

from collections import defaultdict, deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # numCourses = 2, prerequisites = [[1,0]]
        #  0 -> 1: t
        # numCourses = 2, prerequisites = [[1,0],[0,1]]
        #  0 -> 1 -> 0
        #  0 -> 1  -> 2 ,3 -> 4
        #    base case node == None
        #    recursive case
        #      neighbour
        #   add node to list 
        # # 
        #        #  adjacency list
        #  0 -> 1
        #  1  -> 2 ,3
        #  2  -> None
        #  3  -> 4
        #  4 -> None
        #  seen = {}
        #  res = []
        #  dfs 0 
        #      seen = {0}
        #      dfs (1)
        #         seen = {1}
        #         dfs(2)
        #           seen = {0 1 2} base case
        #         dfs(3)
        #           seen = {0 1 2 3}
        #           dfs(4)
        #            seen = {0 1 2 3 4}
        #            base case
        #            res = [4]
        #        res = [4, 3, 2]
        #       res = [4, 3, 2, 1]
        #   res = [4, 3, 2 ,1 ,0]
        #  res =  reverse(res) 
        #  len(Res) == n else -1
        # Time Complexity:(n * n)
        # Space Complexity: (n)

        # graph
        return self.dfs(numCourses, prerequisites)
    
    # Time Complexity: O(m + n)
    # Space Complexity : O(m+ n)
    def kahn_algorithm(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        adjList = defaultdict(list)

        for course, prereq in prerequisites:
            adjList[prereq].append(course)
            indegree[course] += 1
        
        queue = deque()

        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        nodeVisited = 0

        while queue:
            node = queue.popleft()
            nodeVisited += 1

            for neighbour in adjList[node]:
                indegree[neighbour] -= 1
                if indegree[neighbour] == 0:
                    queue.append(neighbour)
        
        return nodeVisited == numCourses

    # Time Complexity: O(m + n)
    # Space Complexity : O(m+ n)
    def dfs(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adjList = defaultdict(list)

        for course, prereq in prerequisites:
            adjList[prereq].append(course)
        
        visit = [False]  * numCourses
        inStack = [False] * numCourses

        def dfs(node):
            if inStack[node]:
                return True
            if visit[node]:
                return False
            
            visit[node] = True
            inStack[node] = True

            for neighbor in adjList[node]:
                if dfs(neighbor):
                    return True
            
            inStack[node] = False
            return False

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

Dry Run