Topological Sort LeetCode Pattern Guide — Course Schedule and Dependency Problems

This topological sort LeetCode pattern guide is for Course Schedule and dependency problems: tasks with prerequisites, packages with imports, recipes with ingredients, or jobs that must run after other jobs. Topological sort produces an order of nodes in a directed acyclic graph so that every prerequisite appears before the thing that depends on it. If the graph contains a directed cycle, no valid order exists.

The pattern is powerful because it turns dependency chaos into two questions: can I process something with no remaining prerequisites, and did I process every node? The hard parts are building the graph in the correct direction and explaining how cycle detection works.

What topological sort means

A topological order is a linear ordering of a directed graph where for every edge a -> b, a comes before b. The graph must be a DAG, a directed acyclic graph. If a depends on b, be careful: the edge direction could be b -> a if you mean “b must happen before a.”

For Course Schedule, a pair [course, prerequisite] means you must take prerequisite before course. A natural graph is:

prerequisite -> course

Then indegree of a course means how many prerequisites remain.

Kahn's algorithm: BFS with indegrees

Kahn's algorithm is the most interview-friendly topological sort. Build adjacency lists and indegree counts. Start with all nodes whose indegree is zero. Repeatedly remove one, append it to the order, and decrement indegrees of neighbors. Any neighbor whose indegree becomes zero is ready.

from collections import deque

def topo_order(n, prerequisites):
    graph = [[] for _ in range(n)]
    indeg = [0] * n

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

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []

    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

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

The invariant is: the queue contains exactly the nodes whose prerequisites have all been satisfied by already processed nodes. If a cycle exists, every node in that cycle keeps at least one unresolved incoming edge, so the algorithm cannot process all nodes.

Course Schedule I and II

Course Schedule I asks whether all courses can be finished. You only need a boolean:

def can_finish(num_courses, prerequisites):
    return len(topo_order(num_courses, prerequisites)) == num_courses

Course Schedule II asks for one valid order. Return the list from Kahn's algorithm, or an empty list if there is a cycle.

Multiple valid orders may exist. That is not a problem. Unless the prompt asks for lexicographically smallest order, any valid topological order is acceptable.

If lexicographically smallest order is required, use a min-heap instead of a queue for zero-indegree nodes.

DFS cycle detection alternative

DFS topological sort uses node states:

• 0 = unvisited
• 1 = visiting, currently in recursion stack
• 2 = done, fully processed

A back edge to a visiting node means a directed cycle.

def can_finish_dfs(n, prerequisites):
    graph = [[] for _ in range(n)]
    for course, pre in prerequisites:
        graph[pre].append(course)

    state = [0] * n

    def dfs(node):
        if state[node] == 1:
            return False
        if state[node] == 2:
            return True
        state[node] = 1
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        state[node] = 2
        return True

    return all(dfs(i) for i in range(n))

To produce an order with DFS, append each node after exploring neighbors, then reverse the result. Kahn's algorithm is often easier to reason about for prerequisites, but DFS is useful when the question is framed directly as cycle detection.

Building the graph correctly

Most topological sort bugs happen before the algorithm starts. Use this checklist:

1. What does each pair mean in plain English?
2. Which item must come first?
3. Draw the edge from earlier item to later item.
4. Increment indegree of the later item.
5. Initialize all nodes, even nodes with no edges.

For recipes, an edge might go ingredient -> recipe. For package installation, dependency -> package. For alien dictionary, edge direction comes from the first differing character between two adjacent sorted words: if abc appears before abd, then c -> d.

Do not add edges for every differing character in alien dictionary. Only the first difference determines ordering; later characters are irrelevant once the word order is decided.

Cycle detection explained

A directed cycle means a node eventually depends on itself. In Kahn's algorithm, cycles reveal themselves because no node in the cycle can ever reach indegree zero. The processed count stays below n.

In DFS, cycles reveal themselves when recursion reaches a node that is already being visited. That means the current path loops back to an ancestor.

An interview-ready explanation:

“If there is a cycle, every node in that cycle has at least one prerequisite inside the cycle. None of them can be the first completed node, so Kahn's algorithm will leave them unprocessed. Therefore processed == n is equivalent to no directed cycle for the dependency graph.”

Dependency problem variations

Parallel semesters

If you process the queue level by level, each level can represent one semester or one batch of jobs that can run in parallel. Count levels instead of just returning order.

semesters = 0
while q:
    for _ in range(len(q)):
        node = q.popleft()
        # release neighbors
    semesters += 1

If there is a limit on how many courses can be taken per semester, the problem becomes harder and may require DP or bitmask search.

Eventual safe states

This looks like topological sort on a reversed graph. Terminal nodes are initially safe. Reverse edges and peel nodes whose outgoing risk count drops to zero.

Minimum height trees

This is not a directed topological sort, but it uses a similar peel-the-leaves idea on an undirected tree. Remove leaves layer by layer until one or two centers remain.

Alien dictionary

Build character nodes, add edges from the first differing character in adjacent words, and then topologically sort. Also handle the invalid prefix case: "abc" before "ab" is impossible because a longer word cannot come before its exact prefix in lexicographic order.

Common traps

• Reversing edges accidentally. Decide whether indegree means prerequisites remaining or dependents remaining.
• Ignoring isolated nodes. A course with no prerequisites must still appear in the order.
• Using undirected cycle logic. Directed cycle detection is different from undirected parent tracking.
• Adding duplicate edges. Duplicates can inflate indegree. Use sets if input may repeat dependencies.
• Assuming unique order. Many DAGs have multiple valid orders.
• Forgetting the prefix rule in alien dictionary. No graph edge can fix invalid word order.
• Returning partial order on cycle. If processed count is short, return failure, not the partial list.

Complexity

For n nodes and e edges, topological sort is O(n + e) time and O(n + e) space. Each node enters the queue once. Each edge is considered once when its source is processed.

If you use a heap for deterministic smallest-order output, runtime becomes O((n + e) log n) in the worst case because queue operations cost more.

Practice roadmap

Start with:

1. Course Schedule I: boolean cycle detection with Kahn.
2. Course Schedule II: return an order.
3. Alien Dictionary: graph construction and invalid prefixes.
4. Find Eventual Safe States: reverse graph thinking.
5. Parallel Courses: level-by-level processing.
6. Recipe or build-system problems: mapping strings to nodes.

After each problem, write the edge direction in one sentence. If you cannot, you are likely to reverse the graph.

How to talk about topological sort in interviews and resumes

In an interview:

“I’ll model each prerequisite as an edge from prerequisite to course. Indegree counts unmet prerequisites. Nodes with indegree zero are ready to process. Each time I process a node, I release its dependents. If I process all nodes, the graph is acyclic; otherwise a cycle prevented some nodes from becoming ready.”

On a resume:

• “Modeled workflow dependencies as a directed acyclic graph and used topological sorting to compute valid execution order.”
• “Detected circular dependencies in configuration data by tracking indegrees and unresolved nodes.”
• “Built batch scheduling logic that grouped zero-dependency tasks into parallel execution waves.”

Topological sort is a dependency-management pattern. The algorithm is straightforward once the graph is correct. Spend extra time translating the prompt into edge direction, indegree meaning, and cycle behavior; that is where interview correctness usually lives.

Graph construction drills

Practice translating prompts before coding. If the prompt says “task A must be completed before task B,” draw A -> B and increment indegree of B. If it says “course C has prerequisite P,” draw P -> C. If it says “package X imports package Y,” usually Y -> X because Y must be installed first. Write that sentence as a comment above your loop. It prevents the common bug where the traversal still returns an order, but the order is reversed for the prompt.

Also decide whether duplicate dependencies are possible. If input can contain [1,0] twice, a list-based graph increments indegree twice and requires two artificial releases. Use a set per node or a global edge set when duplicates are not semantically meaningful.

When topological sort is not enough

Some dependency problems add optimization constraints after the ordering question. If each task has a duration and you need the earliest finish time, topological sort is only the traversal backbone; you also need dynamic programming over the DAG. If only k courses can be taken per semester, choosing which ready courses to take becomes a combinatorial decision. If dependencies can be removed dynamically, rebuilding indegrees may be necessary. In interviews, call this out: “First I’ll detect whether a valid order exists with topological sort. If we need the minimum schedule length with limits, that is an additional optimization layer.” This keeps the pattern correctly scoped.

Validation examples

Test an empty prerequisite list, a simple chain 0 -> 1 -> 2, a diamond where two prerequisites feed one course, and a cycle like 0 -> 1 -> 0. For alien dictionary, always test the invalid prefix case and a case with isolated characters that have no edges but still must appear in the output.

Related guides

• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Divide and Conquer LeetCode Pattern Guide — Merge Sort, Quickselect, and Recursion — A practical LeetCode pattern guide for divide and conquer: master recursive contracts, merge sort variations, quickselect, tree recursion, complexity, and common interview traps.
• Monotonic Stack LeetCode Pattern Guide — Next Greater Element and Histogram Problems — Learn the monotonic stack pattern for next greater element, daily temperatures, stock spans, and largest rectangle in histogram problems, with templates and interview traps.
• Trie LeetCode Pattern Guide — Prefix Search, Autocomplete, and Word Problems — A practical trie pattern guide for LeetCode interviews: when prefix trees beat hash sets, how to code the templates, and how to handle autocomplete, wildcard search, and board word problems.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.