How Do You Solve Course Schedule II with Topological Sort?

Prompt and Scope

There are numcourses courses labeled from 0 through numcourses - 1. A prerequisite pair [course, prerequisite] means that prerequisite must be completed before course. Return any order that completes every course. Return an empty list if no such order exists.

For this version, assume 0 <= num_courses <= 2000, every course label is valid, the pairs are distinct, and the input contains no self-edge. Return an empty list when num_courses == 0. For num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]], both [0, 1, 2, 3] and [0, 2, 1, 3] are correct. For [[1, 0], [0, 1]], the two courses depend on each other, so the only valid response is an empty list.

This is a representative general software-engineering coding problem. Its core task is translating natural-language dependencies into a directed graph and deciding whether that graph is acyclic. The base problem asks for any valid order. It does not ask for the lexicographically smallest order, course durations, or a limit on concurrent courses.

What the Interviewer Evaluates

The first signal is edge direction. [course, prerequisite] becomes prerequisite -> course, because completing the prerequisite releases the course. A reversed graph may still produce a permutation, but that permutation encodes the opposite constraint.

The second signal is whether the candidate can derive indegree from the phrase “currently available course.” A course's indegree is the number of direct prerequisites that remain unsatisfied. Only a zero-indegree course is ready. Completing one course decrements only the indegrees of its direct successors. A strong answer explains this state instead of merely saying “use BFS.”

The third signal is cycle detection. An empty queue does not justify returning a partial answer. All nodes were processed only when the result length equals the course count. A shorter result means that the remaining subgraph has no zero-indegree node and must contain a directed cycle.

The interviewer will also check complexity, boundaries, and contract discipline. An adjacency-list implementation uses O(V + E) time and space. deque.popleft() keeps removal from the front of the queue constant-time. Tests should cover multiple valid orders, disconnected courses, empty input, and a long dependency chain.

Clarifying Questions Before Answering

• Can I return any order, or must it be lexicographically smallest? A normal queue returns any

order. The smallest order needs a min-heap and changes the time bound to O(E + V log V).

• Can prerequisite pairs repeat? This problem says they are distinct. If they can repeat, either

keep duplicate adjacency entries and count both in indegree, or deduplicate both structures while building the graph. Deduplicating only one side makes the counts inconsistent.

• Can labels be invalid, or can the input contain self-edges? The base problem assumes validated

input. A defensive API should distinguish an invalid request from a valid graph that contains a cycle, instead of silently mapping both cases to an empty list.

• Do we need one order or every valid order? Finding one order is a linear graph traversal.

Enumerating every order branches over all currently available nodes and can produce nearly factorially many results.

• Can courses run in parallel? The base result is a linear order. With unlimited semester

capacity, minimum semesters require level-by-level queue processing. With course durations, the problem becomes a longest-path computation on a DAG.

• Does the graph fit in memory? An adjacency list is straightforward for V <= 2000. External

storage or partitioned processing would be a different system problem.

30-Second Answer Framework

“I will model each course as a node and turn [course, prerequisite] into an edge from the prerequisite to the course. I will also count each course's indegree. I put every zero-indegree course in a queue, repeatedly remove one into the result, decrement its successors' indegrees, and enqueue a successor when its indegree becomes zero. The queue contains exactly the unprocessed courses whose prerequisites are all complete, so every choice is safe. If the result contains every course, I return it; otherwise the remaining nodes contain a cycle, so I return an empty list. With an adjacency list, both time and extra space are O(V + E).”

Step-by-Step Deep Dive

A direct solution repeatedly scans every unselected course and chooses one whose prerequisites have already appeared. Even with a set of completed courses, each round may inspect every edge. A chain can require V rounds, making the worst case O(VE). The repeated recomputation of satisfied dependencies is the bottleneck.

Kahn's algorithm maintains that information incrementally as indegree. Let graph[u] contain the courses that may be released after completing u, and let indegree[v] count the direct prerequisites of v that remain. For each [course, prerequisite], append course to graph[prerequisite] and increment indegree[course].

The algorithm maintains two invariants:

1. indegree[v] equals the number of edges into v from unprocessed nodes.
2. The queue contains all and only the unprocessed courses whose remaining indegree is zero.

The initial count satisfies the first invariant, and enqueuing every zero-indegree node establishes the second. When course u is removed, no unprocessed prerequisite points into it, so appending it to the result is safe. Removing u is represented by visiting graph[u] and decrementing each successor's indegree. A successor is enqueued exactly when its count first reaches zero, preserving both invariants.

from collections import deque


def find_course_order(
    num_courses: int,
    prerequisites: list[list[int]],
) -> list[int]:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1

    ready = deque(
        course for course, degree in enumerate(indegree) if degree == 0
    )
    order: list[int] = []

    while ready:
        course = ready.popleft()
        order.append(course)

        for dependent in graph[course]:
            indegree[dependent] -= 1
            if indegree[dependent] == 0:
                ready.append(dependent)

    return order if len(order) == num_courses else []

If every course is removed, the invariants guarantee that all of its prerequisites appeared earlier, so the result is valid. If the result is shorter than V, every node in the remaining finite subgraph has positive remaining indegree. Start at any remaining node and repeatedly follow one incoming edge. A finite graph must eventually repeat a node, and the repeated segment is a directed cycle. Therefore no complete order exists. The length check is also the cycle test.

Each node enters and leaves the queue at most once. Each edge is handled once while building the graph and once while releasing successors, so the time is O(V + E). The adjacency list, indegree array, queue, and result use O(V + E) space. The implementation uses deque because Python's list.pop(0) shifts the remaining elements and can make a queue operation linear.

Adversarial validation should check properties rather than one fixed answer. A successful result must contain exactly V unique labels, and the position of prerequisite must be smaller than the position of course for every pair. Cover an empty graph, one node, all-independent nodes, a long chain, a diamond with multiple orders, disconnected components, and a directed cycle. The diamond case catches tests that incorrectly require one particular topological order.

DFS can also compute a topological order. Use white, gray, and black states; an edge to a gray node detects a cycle, and nodes enter the result on recursive exit before the postorder is reversed. DFS is useful when the API must also report a concrete cycle, but a long chain can exceed Python's recursion limit. Kahn's algorithm exposes the set of currently available courses and extends naturally to parallel semesters, making it the more direct choice here. For a tiny graph where only feasibility matters, repeated scanning can be shorter; state its worst-case cost instead of calling it linear.

High-Quality Sample Answer

“I will first confirm that any valid order is acceptable and assume the labels and distinct edges are valid. Each [course, prerequisite] pair creates an edge from the prerequisite to the course. A course's indegree then measures how many direct prerequisites are still incomplete.

I build an adjacency list and indegree array, then add every zero-indegree course to a deque. In the loop, I remove a course into the answer and decrement the indegrees of its successors. A successor is enqueued only when its indegree becomes zero. The key invariant is that the queue contains exactly the courses with no unfinished prerequisite, so choosing from it cannot violate an edge.

I cannot return unconditionally when the queue empties. If the answer length equals the number of courses, every dependency was satisfied. If it is shorter, all remaining nodes still have an incoming edge. Following incoming edges in a finite graph must revisit a node, which proves that a cycle remains, so I return an empty list.

The adjacency list processes every node and edge a constant number of times, giving O(V + E) time and O(V + E) space. I would test an empty graph, one node, a long chain, a diamond with multiple answers, disconnected components, and a two-node cycle. For multiple answers, I validate every prerequisite's relative position instead of comparing with one fixed array.”

Common Mistakes

• Building course -> prerequisite → a course may appear before its prerequisite → **Build

prerequisite -> course, following the question “what does completing this node release?”**

• Starting only from course 0 → disconnected components disappear → **Scan every node and enqueue

every initial zero-indegree node.**

• Returning a partial result when the queue empties → cyclic input is reported as success → **Return

an order only when len(order) == num_courses.**

• Enqueuing a node more than once → the result contains duplicate courses → **Enqueue only on the

transition from indegree 1 to 0.**

• Using list.pop(0) as the queue → large inputs repeatedly shift elements → **Use

deque.popleft().**

• Comparing output with one fixed topological order → another valid order fails the test → **Check

uniqueness, length, and every edge's relative positions.**

• Deduplicating the graph but not indegree, or vice versa → counts disagree under a duplicate-edge

contract → Keep duplicates consistently or deduplicate each edge during graph construction.

• Claiming O(V) extra space → the adjacency list still stores all edges → **Report O(V + E) for

this sparse-graph representation.**

• Using DFS without an in-progress state → cycle nodes recurse repeatedly or finish incorrectly →

Use at least three states to separate active and completed nodes.

Follow-Ups and How to Handle Them

Follow-up 1: How would you return the lexicographically smallest valid order?

Replace the queue with a min-heap. Taking the smallest label among all currently available nodes gives the lexicographically smallest result by a greedy exchange argument. Edge work stays O(E), while heap insertion and removal make the total O(E + V log V). A normal queue remains simpler and faster when any order is accepted.

Follow-up 2: With unlimited parallel courses per semester, what is the minimum semester count?

Process the queue by its current level size. Courses in one level complete in the same semester, and their newly released zero-indegree successors form the next level. Increment the semester count per level. This works only when all courses take equal time and semester capacity is unlimited. A limit of at most k courses per semester makes simple level processing insufficient for global optimality.

Follow-up 3: Courses have different durations. How do you find the earliest graduation time?

First obtain a topological order, then run dynamic programming in that order. A course's earliest start is the maximum earliest-finish time among its prerequisites; add its own duration to get its earliest finish. The answer is the maximum finish time. Kahn levels are not enough because a ten-week course and a one-week course cannot be treated as equal units.

Follow-up 4: How would you return one concrete dependency cycle?

Kahn's algorithm proves that the remaining subgraph has a cycle but does not retain its path. Run a three-color DFS on the remaining nodes and store parent pointers. On an edge to a gray node, follow parents back to reconstruct a cycle. If diagnostics are a primary requirement, a parent-tracking DFS topological sort can be used from the start.

Follow-up 5: How would you maintain an order as prerequisite edges are added?

For infrequent updates, rerunning the O(V + E) algorithm after each insertion is the most reliable and easiest to verify. For a large graph with frequent updates, store each node's current position. An edge already consistent with that order needs no change; an inconsistent edge requires reachability checking and reordering within the affected interval. Dynamic topological ordering is complex, so its cost should be justified by measured graph size and update rate.

Follow-up 6: How would you enumerate every valid course order?

Use backtracking. At each step, branch over all current zero-indegree nodes, choose one temporarily, update its successors, recurse, and restore the indegrees. This avoids invalid permutations, but the number of valid orders can approach V!, so the running time is at least proportional to the output. Confirm a small limit first and ask whether the caller actually needs a count, a sample, or only the first k orders.