0
\$\begingroup\$

I am working on the CourseSchedule problem

Course Schedule - LeetCode

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

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[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: 2, [[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.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

My solution and detailed comments

from typing import List
#from collection import deque 
class Solution:
    def canFinish(self, numCourses: int, prequisites: List[List[int]]) -> bool:
        """
        :rtype:bool
        """
        #base case 
        if numCourses == None or prequisites == None:  return None  

        #Construct a directed graph from `prerequisites`.
        #initiate the graph, The nodes are `0` to `n-1`(nodes are origins)
        graph = [[] for _ in range(numCourses)]
        # there is an edge from `i` to `j` if `i` is the prerequisite of `j`. 
        for x, y in prequisites:
            graph[x].append(y)   
        #hold the paint status
        #we initiate nodes which have not been visited, paint them as 0
        paint = [0 for _ in range(numCourses)]
        #if node is being visiting, paint it as -1, if we find a node painted as -1 in dfs,then there is a ring 
        #if node has been visited, paint it as 1

        def dfs(i):
            #base cases 
            if paint[i] == -1: #a ring 
                return False
            if paint[i] == 1: #visited 
                return True
            paint[i] = -1 #paint it as being visiting.
            for j in graph[i]: #traverse i's neighbors 
                if not dfs(j): #if there exist a ring.
                    return False
            paint[i] = 1 #paint as visited and jump to the next.
            return True
        for i in range(numCourses):
            if not dfs(i): #if there exist a ring.
                return False
        return True

get scores

Runtime: 48 ms, faster than 87.39% of Python3 online submissions for Course Schedule.
Memory Usage: 16.2 MB, less than 11.61% of Python3 online submissions for Course Schedule.

How could improve the memory usage?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.