Leetcode: 210. Course Schedule II

Patterns

Pattern: Graph problem.
Pattern: Ordering problem.

Prompts

Can we formulate the problem as a classical problem? Topological Sort.

Solution

Build the graph of dependencies and then run Topological Sort to find the order of courses to take. Time complexity is \(O(n)\) and space is \(O(m)\).

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        A = {u: [] for u in range(numCourses)}
        in_degree = [0] * numCourses
        for u, v in prerequisites:
            A[v].append(u)
            in_degree[u] += 1

        queue = [u for u in range(numCourses) if in_degree[u] == 0]
        ans = []
        for u in queue:
            ans.append(u)
            for v in A[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
        return ans if len(ans) == numCourses else []