Ttykuu

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?