Course Schedule II

Return one valid order for completing every course.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Course Schedule II: Emit only zero-indegree courses; remove each outgoing edge and enqueue a neighbor exactly when its count reaches zero.

Input and goalReturn one valid order for completing every course.

Build the prerequisite DAGEdges are 0->1, 0->2, 1->3, and 2->3; indegrees are [0,1,1,2], so ready=[0].

from\to01230-0->10->2-1---1->32---2->33----

examplecourse_count=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]edgeMeaningmatrix cell is prerequisite -> courseindegree[0,1,1,2]ready[0]order[]

Recognize it

Directed prerequisites require one valid linear order; a cycle is present when some vertex never reaches zero indegree.

Keep true

Every ready vertex has zero incoming edges from un-emitted vertices, and order is a valid topological prefix; each outgoing edge is removed exactly once.

Reuse it

Remove resolved requirements one edge at a time and enqueue exactly on transition to zero; retain the emitted prefix when an order, not just feasibility, is required.

Pattern: Topological sort that saves the order.

Simple idea: This is Course Schedule with one extra action. Append each ready course to the answer. If a cycle prevents some courses from becoming ready, return an empty list.

from collections import deque

def find_order(course_count: int, prerequisites: list[list[int]]) -> list[int]:
   graph = [[] for _ in range(course_count)]
   indegree = [0] * course_count

   for course, prerequisite in prerequisites:
      graph[prerequisite].append(course)
      indegree[course] += 1

   ready = deque(course for course in range(course_count) if indegree[course] == 0)
   order = []
   while ready:
      course = ready.popleft()
      order.append(course)
      for next_course in graph[course]:
         indegree[next_course] -= 1
         if indegree[next_course] == 0:
            ready.append(next_course)

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

Cost: $O(V+E)$ time and space.