Return a valid order to take every course. Count each course's prerequisites, start with the ones at zero, and unlock the rest as you go.
▼The problem
LeetCode 210 (Medium). There are numCourses courses, numbered 0 to numCourses - 1; a pair [a, b] means take b before a. Return an order that takes every course, or [] if there is none (the pairs contain a cycle). It is the sequel to ../course-schedule (LC 207, overworld.jsx), which only asked whether you can finish.
Examples (LeetCode's): n = 2, [[1,0]] → [0,1]; n = 4, [[1,0],[2,0],[3,1],[3,2]] → [0,1,2,3] ([0,2,1,3] is also valid); n = 1, [] → [0].
The solution
from collections import deque
def find_order(n, prereqs):
after = [[] for _ in range(n)]
indeg = [0] * n
for a, b in prereqs:
after[b].append(a) # b unlocks a
indeg[a] += 1
queue = deque(c for c in range(n) if indeg[c] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for d in after[c]:
indeg[d] -= 1
if indeg[d] == 0:
queue.append(d)
return order if len(order) == n else []Transcript
Course Schedule Two. Courses are numbered from zero; a pair a, b means take b before a. Return an order that takes them all, or an empty list if none exists. Course Schedule asked if you can finish; now print the order.
Two courses, one needs zero: zero, then one. Four courses: one and two need zero, three needs both. Zero, one, two, three works; so does zero, two, one, three. One course: just zero. If zero and one need each other, return empty.
The slow way: scan for a course whose prerequisites are all done, take it, then scan again. With V courses and E pairs, that's V scans of V plus E each.
The key idea is Kahn's algorithm. Each course's in-degree counts the prerequisites it still waits on. Queue every course at zero. Pop one, add it to the order, and each course that needs it drops by one. Any that reach zero join the queue.
In code: count the in-degrees, queue the zeros, then pop, append, decrement, enqueue. If the order comes up short, a cycle blocked the rest: return empty.
Now the four courses. Only zero starts at zero. Pop zero: one and two drop to zero and join. Pop one: three drops to one. Pop two: three reaches zero. Pop three. Order: zero, one, two, three.
Each course is queued once and each pair checked once: O of V plus E time, and V plus E space for the lists.
Count the waits, queue the zeros, peel them off. That's Course Schedule Two.