Course Schedule II (LeetCode 210)

The problem

There are n courses labelled 0 to n - 1. Each pair [a, b] means “take b before a”. Return one order in which you can take all the courses. If no such order exists (the prerequisites contain a cycle), return an empty list. Any valid order is accepted.

Input:  n = 4, prereqs = [[1,0], [2,0], [3,1], [3,2]]
Output: [0, 1, 2, 3]

Course 0 has no prerequisites. Courses 1 and 2 need only 0. Course 3 needs both 1 and 2. [0, 2, 1, 3] would also be correct.

How to think about it

Start with brute force. Try every permutation of the courses and return the first one that respects every prerequisite. That’s O(n!·E), far too slow.

The key insight: the order Kahn’s algorithm removes courses in is a topological order. Model prerequisites as edges b → a. A course with in-degree 0 has nothing left to wait for, so it can go next in the schedule. Taking it removes its outgoing edges, which may free up other courses. Each time you pop a course from the queue, all of its prerequisites have already been popped, because its in-degree only reached 0 once they were. So appending each popped course to a list builds a valid order.

Detecting the impossible case is free. If the graph has a cycle, the courses on it never reach in-degree 0 and never enter the queue. So when the queue empties, len(order) < n means some courses are stuck: return [].

Which pattern is this? Topological sort. The tell is “return an order that respects dependencies”. It’s Course Schedule (LeetCode 207) with one change: keep the order instead of just counting.

Approach

1. Build the adjacency list b → a and the in-degree array.
2. Queue every course with in-degree 0.
3. Pop a course, append it to order, and decrement the in-degree of each course that depends on it. Push any that hit 0.
4. Return order if it contains all n courses, otherwise [].

Solution

from collections import defaultdict, deque
def find_order(n, prereqs):
    adj = defaultdict(list); indeg = [0]*n
    for a, b in prereqs: adj[b].append(a); indeg[a] += 1      # b must come before a
    q = deque([i for i in range(n) if indeg[i] == 0]); order = []
    while q:
        u = q.popleft(); order.append(u)                       # all of u's prerequisites are done
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []                    # short order means a cycle
# find_order(4, [[1,0],[2,0],[3,1],[3,2]]) -> [0,1,2,3]

Dry run

On n = 4, prereqs = [[1,0],[2,0],[3,1],[3,2]]:

All four courses are placed, so the order is returned. With [[1,0],[0,1]] the queue starts empty, order stays [], and the function returns [].

Complexity

• Time: O(V + E). Each course enters and leaves the queue once, and each edge is processed once.
• Space: O(V + E) for the adjacency list, in-degrees, queue and output.

Edge cases and pitfalls

• No prerequisites: any order works. The code returns [0, 1, …, n-1].
• One course, no edges returns [0].
• Reversed edges. If you build a → b, you’ll get a valid order backwards. Test with a two-course example to catch it.
• Returning a partial order when there’s a cycle. The problem wants [], so check the length.
• DFS alternative. Post-order DFS, reversed, is also a topological order, but you need a three-state visited array to catch cycles. Kahn’s version handles both in one loop.

Related problems

• Course Schedule (LeetCode 207): the yes/no version of the same question.
• Alien Dictionary (LeetCode 269): derive the edges from word order, then return the topological order.
• Reconstruct Itinerary (LeetCode 332): another ordering problem on a directed graph, solved with post-order DFS.