LeetCode #210 Medium

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.

graphstopological-sortbfs

Open on LeetCode ↗

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1from collections import deque
▶2 
▶3class Solution:
▶4    def findOrder(self, numCourses, prerequisites):
▶5        adj = [[] for _ in range(numCourses)]
▶6        indeg = [0] * numCourses
▶7        for a, b in prerequisites:
▶8            adj[b].append(a)
▶9            indeg[a] += 1
▶10        q = deque(i for i in range(numCourses) if indeg[i] == 0)
▶11        order = []
▶12        while q:
▶13            c = q.popleft()
▶14            order.append(c)
▶15            for nxt in adj[c]:
▶16                indeg[nxt] -= 1
▶17                if indeg[nxt] == 0:
▶18                    q.append(nxt)
▶19        return order if len(order) == numCourses else []

05

Edge cases

A cycle exists

The queue empties early, the result list is shorter than numCourses, and an empty array is returned as specified.

No prerequisites

Every course is takeable from the start, so any permutation is valid; the algorithm returns [0, 1, ..., n-1].

Multiple valid orderings

All are accepted. Using a stack instead of a queue produces a different — still valid — order.

Disconnected components

Handled naturally, since all zero-in-degree vertices are seeded regardless of which component they belong to.

06

Complexity

Time

O(V + E)

Space

O(V + E)

Identical to Course Schedule I, with the pop sequence retained instead of only its length.