LeetCode (Course Schedule I, II, III, IV)

1. Course Schedule(Medium)

    # Time O(E+V) Space O(E+V), runtime = 212 ms
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

if not prerequisites: return True

pre_course_dict = collections.defaultdict(list)
cc_dict = collections.defaultdict(list)
for c, p in prerequisites:
pre_course_dict[p].append(c)
cc_dict[c].append(p)

result = []
in_progress = collections.deque([])
# find the node donnot have pre requests
vs = []
for v in pre_course_dict.values():
vs += v
for k in pre_course_dict.keys():
if k not in vs:
in_progress.append(k)

while in_progress:
pre = in_progress.popleft()
result.append(pre)
for course in pre_course_dict[pre]:
cc_dict[course].remove(pre)
if not cc_dict[course]:
in_progress.append(course)
return len(result) == len(pre_course_dict)

2. Course Schedule II(Medium):

    # Time O(V+E) Space O(V+E)
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

pre_dict = collections.defaultdict(list)
course_dict = collections.defaultdict(list)
for [course, pre] in prerequisites:
pre_dict[pre].append(course)
course_dict[course].append(pre)

todo = collections.deque([])
results = []
for i in range(numCourses):
if i not in course_dict:
todo.append(i)
while todo:
c1 = todo.popleft()
results.append(c1)

if c1 in pre_dict:
for c2 in pre_dict[c1]:
course_dict[c2].remove(c1)
if course_dict[c2] == []:
todo.append(c2)

if len(results) < len(course_dict):
return []

return results

3. Course Schedule III(Hard):

4. Course Schedule IV(Medium):

Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store