210. Course Schedule II - cocoder39/coco39_LC GitHub Wiki

210. Course Schedule II

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        in_degrees = {}
        for i in range(numCourses):
            in_degrees[i] = 0
        
        adjacent_list = collections.defaultdict(list)
        for prerequisite in prerequisites:
            adjacent_list[prerequisite[1]].append(prerequisite[0])
            in_degrees[prerequisite[0]] += 1
            
        queue = collections.deque()
        for key in in_degrees:
            if in_degrees[key] == 0:
                queue.append(key)
        
        order = []
        while queue:
            i = queue.popleft()
            order.append(i)
            for j in adjacent_list[i]:
                in_degrees[j] -= 1
                if in_degrees[j] == 0:
                    queue.append(j)
        
        if len(order) != numCourses:
            return []
        return order

Edge cases: there are nodes which are not in the prerequisites (ie, no dependency relationship). That said, building in_degrees by iterating the prerequisites could miss those nodes.

Time and space complexity are same as Course Schedule