Course Schedule II — The Degree Planner

Boss 9: The Degree Planner

Boss 8 detected the knot. This boss produces the untangled rope. A yes/no answer isn't a plan, and "in what order?" turns out to be its own algorithm: topological sort, the canonical tool for putting any DAG in line. It installs indegree bookkeeping, a BFS-flavored ordering called Kahn's algorithm, and a free bonus: the sort detects cycles as a side effect, so it quietly answers Boss 8 too.

The story

Same catalog, but now the advisor wants dates on paper:

course 0  Intro            needs nothing
course 1  Data Structures  needs 0
course 2  Discrete Math    needs 0
course 3  Algorithms       needs 1 and 2
course 4  Compilers        needs 3

The advisor's method is beautifully dumb. Count each course's unmet prereqs. Anything at zero is takeable right now. Take one, cross it off, and every course waiting on it has one less unmet need, maybe dropping to zero itself:

unmet needs:  0:0  1:1  2:1  3:2  4:1

ready [0]      take 0 → 1 and 2 drop to zero
ready [1, 2]   take 1 → 3 drops to one
ready [2]      take 2 → 3 drops to zero
ready [3]      take 3 → 4 drops to zero
ready [4]      take 4

plan: 0, 1, 2, 3, 4

And here's the elegance. If the catalog has a knot, the knotted courses never reach zero, each one eternally waiting on another. The ready list dries up with courses left over, the plan comes up short, and the shortness itself is the cycle alarm.

The problem, dressed up properly

There are numCourses courses labeled 0 to numCourses - 1, and prerequisites[i] = [a, b] means you must take course b before course a. Return any valid order in which you can take all courses. If no valid order exists, return an empty array.

LeetCode 210.

The naive attempt

The advisor's method, minus the insight about when readiness changes. Every round, rescan the entire catalog for any course whose prereqs are all done:

def find_order_naive(num_courses, prerequisites):
    prereqs = [set() for _ in range(num_courses)]
    for course, prereq in prerequisites:
        prereqs[course].add(prereq)
 
    order, done = [], set()
    while len(order) < num_courses:
        progressed = False
        for c in range(num_courses):
            if c not in done and prereqs[c] <= done:   # all prereqs finished?
                order.append(c)
                done.add(c)
                progressed = True
        if not progressed:
            return []            # a full round with no progress: cycle
    return order

Correct, and the stuck-round check even catches cycles. But every round rescans all V courses and rechecks their prereq sets: roughly O(V² + VE). The waste is glaring once you see it, a course's readiness only changes when one of its own prereqs completes. Rescanning courses whose situation cannot have changed is pure busywork. What's missing is a way to be told when a course becomes ready.

The weapon: Kahn's algorithm

Give every course an indegree: the count of prereqs still unmet. Then:

1. Queue every course whose indegree is already zero. Those need nothing, they're semester one.
2. Pop a course, append it to the order. It's officially taken.
3. "Unlock" its dependents: each course waiting on it gets its indegree decremented. Any that hit zero just became ready, into the queue.
4. When the queue dries up, check the count. Order holds all n courses: valid plan. Fewer: a cycle ate the rest, return empty.

from collections import deque
 
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(num_courses)]    # prereq → courses it unlocks
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1
 
    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    order = []
    while queue:
        course = queue.popleft()
        order.append(course)                    # taken, in a legal spot
        for nxt in graph[course]:               # unlock dependents
            indegree[nxt] -= 1
            if indegree[nxt] == 0:              # last prereq just cleared
                queue.append(nxt)
 
    return order if len(order) == num_courses else []

This is BFS in spirit: a frontier of ready nodes, each processed once, unlocking the next frontier. There's also a DFS route: run Boss 8's three-state DFS, record each node in postorder, reverse the list at the end. Same output guarantees. Kahn's tends to win interviews because the cycle check is free and there's no recursion limit to trip over, but know both names.

And notice: LeetCode 207 is literally this function with the last line swapped for return len(order) == num_courses. One algorithm, two bosses.

Watching it work

The advisor's catalog. Edges point prereq → dependent: 0 → 1, 0 → 2, 1 → 3, 2 → 3, 3 → 4.

indegree [0, 1, 1, 2, 1]     queue [0]

pop 0 → order [0]            1 and 2 drop to zero → enqueue both
pop 1 → order [0, 1]         3 drops to one
pop 2 → order [0, 1, 2]      3 drops to zero → enqueue 3
pop 3 → order [0, 1, 2, 3]   4 drops to zero → enqueue 4
pop 4 → order [0, 1, 2, 3, 4]

queue empty, len(order) == 5 == numCourses → valid plan ✓

Feed it Boss 8's knotted catalog instead and courses 1, 2, 3 sit forever at nonzero indegree. The queue drains after the innocents, order holds fewer than n, empty array comes back. The knot never even gets touched.

Gotchas

1. Arrow direction, and this time it matters. Boss 8 forgave a flipped graph, cycle detection doesn't care. Ordering does. Build graph[prereq].append(course): the arrow points from unlocker to unlocked. Reverse it and your plan comes out backwards or nonsensical.

2. Seeding the queue with one node. Every zero-indegree course starts in the queue. Real catalogs have several independent intro courses, and a disconnected cluster with no seed never gets processed.

3. Skipping the final length check. Without len(order) == num_courses you hand back a partial "plan" that silently omits the knotted courses. The contract says empty array, all or nothing.

4. Using list.pop(0) as the queue. That's O(n) per pop, turning O(V + E) into O(V²) on big inputs. deque.popleft() or a read index over a plain list.

5. Expecting one specific answer. [0, 2, 1, 3, 4] is just as valid here, ties can pop in any order. Judges verify validity, not equality, so don't panic when your output differs from the example's.

Complexity

Every course is enqueued and popped once, every edge decremented once, plus the initial counting pass.

Time: O(V + E). Space: O(V + E).

Boss down. XP gained.

The advisor pins the five-line plan to the corkboard. Semester one starts with Intro, the way it always did, except now it's provably correct, and the proof cost one integer per course.

What you walked away with:

• Indegree: unmet dependencies as a single number, making "ready?" an O(1) question
• Kahn's algorithm: queue the ready, take one, unlock dependents, repeat until dry
• Short output means cycle, so topological sort answers Boss 8 for free
• The DFS alternative, postorder reversed, same guarantees, different engine
• When a DAG needs an order, topo sort is the canonical tool, no auditions needed

Next up: Boss 10 — The Village Waterline. Undirected graphs return with a structural question: n pumps, a list of pipes, and one clean test that decides whether the whole network is secretly a tree.