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.
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- All the pairs [ai, bi] are distinct.
Intuition
Course schedule ii extends the previous problem from a yes-or-no answer to an actual ordering: return a valid sequence in which all courses can be taken, or an empty array if none exists. The algorithm is unchanged. Kahn's algorithm already produces a valid order as a by-product — the sequence in which courses are dequeued is a topological order, so the only difference is recording it: - Append each course to a result list as it is processed, and return that list if every course was processed. A course is only enqueued once its in-degree reaches 0, meaning every prerequisite has already been placed. So each course necessarily appears after all its prerequisites, which is exactly the required property. The cycle case is handled by the same count comparison. If the result contains fewer courses than the total, some sit in a cycle and no valid ordering exists — return an empty array, not the partial result. Returning what was collected so far is the most common mistake here, and it produces an incomplete order that looks plausible. Multiple valid orderings usually exist, and any is accepted. Which one appears depends on the order courses leave the queue, so a different but equally correct sequence is not a bug. The DFS alternative also works: run a post-order traversal and reverse the finishing order. The reversal is essential, since a node finishes only after all its dependents, giving exactly the wrong direction. Kahn's algorithm avoids that step entirely, which is why it suits this problem better.
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
Before reading on: price up what the direct approach costs here, then ask what has to finish before a vertex becomes available. Aim for O(V + E) time and O(V + E) space.
Reuse the cycle-detection machinery
This is Course Schedule with output. Kahn's algorithm already produces a valid order as a by-product, so only the recording step is new.
Build the graph and in-degrees
The pair [a, b] means b comes before a, so the edge runs from b to a. Count incoming edges per node as before.
Record courses as they are dequeued
Append each processed course to a result list. A course is enqueued only once every prerequisite has been placed, so the order is automatically valid.
Decrement dependents
Processing a course reduces its dependents' in-degrees, enqueueing any that reach 0. This is what keeps prerequisites ahead of the courses needing them.
Return empty on a cycle
If fewer courses were processed than the total, no ordering exists. Return an empty array, not the partial result — returning what was collected is the usual error here.
Accept any valid ordering
Multiple correct orders typically exist, and which one appears depends on queue order. A different sequence from the expected output is not necessarily wrong.
Cost of the traversal
Each node and edge is handled once, giving O(V + E) time and O(V + E) space for the graph, in-degrees, queue and result.
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.