Course Schedule II

Intuition

A valid study order is exactly a topological ordering of the prerequisite graph. Any course whose indegree is zero has no unfinished prerequisites, so it is safe to schedule immediately. As we lock a course into the order, we remove its influence by lowering the indegree of the courses it unblocks, which may expose new zero-indegree courses. Appending nodes in the sequence they become free naturally produces a valid ordering. If a cycle exists, its members never reach indegree zero, so the produced order will be shorter than numCourses and we return an empty array.

Algorithm walkthrough

1. 1Build an adjacency list and an indegree array; for each [a, b] add edge b -> a and increment indegree[a].
2. 2Seed a queue with all courses whose indegree is 0.
3. 3Pop a course, append it to the output order, and decrement the indegree of each course it points to.
4. 4Enqueue any course whose indegree just became 0, since it is now free of prerequisites.
5. 5When the queue is empty, check whether the order contains all numCourses entries.
6. 6Return the order if it is complete; otherwise a cycle blocked some courses, so return an empty array.

Implementation

from collections import deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque(i for i in range(numCourses) if indegree[i] == 0)
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return order if len(order) == numCourses else []