Course Schedule II
Same setup as Course Schedule, but return an ordering of all courses that respects every prerequisite, or an empty array if none exists.
Open on LeetCode ↗Intuition
Course Schedule already computes the ordering — it just throws it away and returns a boolean. Kahn's algorithm outputs courses precisely when their prerequisites are satisfied, so recording the pop order is a valid topological order. The only change is to collect the sequence and return it, or return an empty list when the count falls short of numCourses, which is the same cycle test as before.
Identical to Course Schedule except you keep the order rather than just counting it. The same stall check applies — a short order means a cycle, and the problem asks for an empty array in that case. One algorithm, two return statements.
Approach
Reuse the machinery verbatim
Build the adjacency list with edges b -> a for each pair [a, b], count in-degrees, and seed a queue with every zero-degree course. Nothing about the graph construction differs from Course Schedule I — worth saying out loud in an interview, because recognising a solved subproblem is faster and less error-prone than rederiving it.
Record the pop order
Every time a course is popped, append it to a result list before decrementing its neighbours. This is valid because a course is only ever popped once all of its prerequisites have already been popped and appended — so every prerequisite appears earlier in the list than the course depending on it, which is exactly the definition of a topological order.
Distinguish success from a cycle
If the result list has numCourses entries, return it. If it is shorter, some courses were never unblocked, meaning a cycle exists and no valid ordering does — return an empty list. Note there is usually more than one correct answer; any order the queue happens to produce is accepted, since the problem asks for an ordering.
Solution & live demo
Common pitfalls
Returning a partial order on a cycle
return order
return order if len(order) == numCourses else []
A cyclic graph still emits the vertices outside the cycle, producing a plausible-looking but incomplete schedule. The length check is the only thing separating a valid answer from a truncated one.
Reversing the output
return order[::-1]
return order
Kahn's algorithm emits vertices in dependency order already — prerequisites leave the queue before the courses that need them. Reversing produces a schedule where every course precedes its own prerequisites.
Using a stack instead of a queue
c = stack.pop()
c = q.popleft()
Any valid topological order is accepted, so LIFO also produces a correct answer here — but it changes which order you get, and if the problem or a test harness expects the BFS-canonical ordering the results won't match. Match the structure to the order you intend to produce.
Edge cases
The queue empties early, the result list is shorter than numCourses, and an empty array is returned as specified.
Every course is takeable from the start, so any permutation is valid; the algorithm returns [0, 1, ..., n-1].
All are accepted. Using a stack instead of a queue produces a different — still valid — order.
Handled naturally, since all zero-in-degree vertices are seeded regardless of which component they belong to.