Course Schedule II

Course Schedule II is the classic topological sort problem. You are given courses with prerequisites and asked for an order in which you can actually take them — or proof that no such order exists because the prerequisites form a cycle.

The slow way first

You could try every permutation of courses and check each one against all the prerequisites. With n courses that is n! orderings — hopelessly slow for anything beyond a handful of courses.

The better question: which course can I take right now? A course is takeable the moment it has no unmet prerequisites. If we keep taking those and removing them, the courses they unlocked become takeable next. That is exactly Kahn algorithm.

The idea: take whatever has no prerequisites left

Model the courses as a directed graph: an arrow u → v means u before v. For each course, count its in-degree — the number of incoming arrows, i.e. how many prerequisites it still has. Repeatedly take a course with in-degree 0, append it to the answer, and decrement the in-degree of everything it points to. A neighbor that drops to 0 is now takeable, so queue it.

If we manage to take every course, the order is valid. If some courses stay stuck above 0, they sit in a cycle of prerequisites that can never be satisfied, so we return [].

Walk through it

Step through the animation. We start by counting in-degrees: courses 0 and 1 need nothing (in: 0), course 2 needs both of them (in: 2), course 3 needs 2 (in: 1). Courses 0 and 1 go into the queue. As each is taken, we relax the arrows out of it — 2 drops from 2 to 1 to 0, then 3 drops to 0. The order fills up to [0, 1, 2, 3].

Pseudocode

build graph and an in-degree count for every course
queue = every course whose in-degree is 0
order = []
while the queue is not empty:
    node = remove a course from the queue
    append node to order
    for each neighbor of node:
        decrement neighbor's in-degree
        if it just hit 0:
            add neighbor to the queue
if order contains every course:
    return order            # valid topological order
return []                   # a cycle blocked some course

The Python solution

def find_order(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for dest, src in prerequisites:
        graph[src].append(dest)
        indeg[dest] += 1
    queue = [c for c in range(numCourses) if indeg[c] == 0]
    order = []
    while queue:
        node = queue.pop(0)
        order.append(node)
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    if len(order) == numCourses:
        return order
    return []

• graph[src] lists the courses unlocked by src; indeg[dest] counts how many prerequisites dest still has.
• The first queue holds every course with zero prerequisites — the only ones takeable at the start.
• Each loop pops a takeable course, appends it to order, and relaxes its edges by decrementing each neighbor.
• A neighbor that hits 0 has all its prerequisites done, so it joins the queue.
• At the end, if order is missing courses, a cycle blocked them and we return [].

Complexity

We visit each course once and walk each prerequisite edge once, so the work is linear in the number of courses plus prerequisites. The extra space is the graph, the in-degree array, and the queue.

When this pattern shows up

Practice