Topological Sort LeetCode Pattern Guide

If a LeetCode problem mentions "prerequisites", "dependencies", "ordering", or "scheduling", there is a very good chance topological sort is the pattern you need. Topological sort leetcode problems are among the most predictable in coding interviews because the problem statement practically tells you what algorithm to use.

The core idea is simple: given a set of tasks with dependency relationships, find an order to complete them such that every prerequisite is finished before the task that depends on it. This appears everywhere in software — package managers resolving dependencies, build systems determining compilation order, university course planners validating prerequisite chains.

Despite sounding academic, topological sort problems follow a consistent template that you can learn once and apply to every variation. In this guide, you will learn two approaches — Kahn's algorithm (BFS) and DFS-based topological sort — and see how they apply to the most commonly asked interview problems.

A topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u appears before v in the ordering. The key requirement is that the graph must be a DAG — it must be directed, and it must have no cycles.

Think of it like a to-do list with prerequisites. If task A must happen before task B, and task B must happen before task C, then the topological ordering is [A, B, C]. If there are no dependency conflicts, the graph is a valid DAG and at least one topological ordering exists.

A directed acyclic graph can have multiple valid topological orderings. For example, if tasks A and B are both independent prerequisites for task C, then both [A, B, C] and [B, A, C] are valid orderings. Most interview problems accept any valid ordering, though some ask for a specific one (like lexicographically smallest).

The critical constraint is that cycles make topological sort impossible. If A depends on B, B depends on C, and C depends on A, there is no valid ordering. Detecting this cycle is a core part of almost every topological sort interview problem.

Kahn's algorithm is the BFS-based approach to topological sort and is the most popular choice in coding interviews. It works by repeatedly removing nodes with zero in-degree — nodes that have no remaining prerequisites — and adding them to the result.

The algorithm starts by computing the in-degree (number of incoming edges) for every node. All nodes with in-degree zero are added to a queue — these are tasks with no prerequisites, so they can be completed immediately. Then you process the queue: dequeue a node, add it to the result, and decrement the in-degree of all its neighbors. If any neighbor's in-degree drops to zero, enqueue it.

When the queue is empty, check the result. If it contains all nodes, you have a valid topological ordering. If it contains fewer nodes than the graph, there is a cycle — some nodes could never reach zero in-degree because they are trapped in a circular dependency.

The DFS-based approach to topological sort uses post-order traversal. You run DFS from each unvisited node, recurse on all neighbors first, and then push the current node onto a stack after all its descendants are processed. The final ordering is the reverse of the stack (or you reverse the result at the end).

The intuition is that in post-order DFS, a node is only added to the result after all nodes it depends on have already been processed. By reversing this post-order, you get a valid topological ordering where dependencies come before the tasks that need them.

Cycle detection with DFS requires three-color marking. Each node starts as "white" (unvisited). When you begin processing a node, mark it "gray" (in progress). When all its neighbors are fully processed, mark it "black" (done). If during DFS you encounter a gray node, you have found a back edge — which means a cycle exists.

The DFS approach is more concise to code but slightly trickier to get right, especially the cycle detection logic. If you forget the gray state and only use a simple visited boolean, you will miss cycles and produce incorrect results.

Topological sort problems appear frequently at top tech companies, and the good news is that the same core pattern applies to all of them. Once you master the template, each new problem is just a matter of building the graph correctly from the problem's input format.

Course Schedule (#207) is the entry-level topological sort problem. You are given a number of courses and a list of prerequisite pairs. The question is simply: can you finish all courses? This is equivalent to asking whether the dependency graph is a DAG — if a valid topological ordering exists, the answer is yes. Kahn's algorithm works perfectly here: if the result contains all courses, return true.

Course Schedule II (#210) extends this by asking you to return the actual ordering. Instead of just checking if a valid ordering exists, you return the sequence. The code is nearly identical to Course Schedule — you just return the result array instead of a boolean.

Alien Dictionary (#269) is a harder variation where you must infer the graph from sorted word pairs. By comparing adjacent words in the dictionary, you extract ordering constraints between characters and then run topological sort on the character graph. This problem tests both graph construction skills and topological sort.

Minimum Height Trees (#310) and Parallel Courses (#1136) are additional variations. Minimum Height Trees uses iterative leaf removal (similar to Kahn's) to find tree centers. Parallel Courses asks for the minimum number of semesters to complete all courses, which maps to the longest path in the DAG — computed by processing level by level with Kahn's algorithm.

Both approaches have the same time and space complexity, so the choice comes down to implementation clarity and what the problem requires. For most interview situations, Kahn's algorithm is the safer choice.

Kahn's algorithm is easier to implement correctly, especially under interview pressure. The BFS loop with an in-degree array is straightforward to code, and cycle detection is built in — just check if the result has all nodes. You do not need to manage recursion state or worry about stack overflow on large graphs.

The DFS approach is more concise and can feel more natural if you are already comfortable with recursive graph traversal. However, the three-color marking for cycle detection is an extra detail that is easy to forget or implement incorrectly. If you only use a boolean visited array (two colors instead of three), you will not detect all cycles.

Use Kahn's as your default approach. Switch to DFS only if the problem specifically benefits from it — for example, if you need to explore all paths or if the problem naturally fits a recursive structure. For standard "can you complete all tasks" or "find a valid ordering" problems, Kahn's is the way to go.

Topological sort is one of the most learnable patterns in coding interviews because the problem template is consistent and the algorithm variations are limited. A focused practice plan can make you confident with these problems in just a few sessions.

Start with Course Schedule (#207) using Kahn's algorithm. Get comfortable building the adjacency list, computing in-degrees, and running the BFS loop. Once you can solve it cleanly, move to Course Schedule II (#210) — the code difference is minimal, but it reinforces the pattern.

After the Course Schedule pair, try Alien Dictionary (#269) to practice building a graph from a non-obvious input format. This problem tests whether you truly understand topological sort versus just memorizing a template. If you can construct the character dependency graph from the word list, the topological sort part is straightforward.

Use YeetCode flashcards to drill the recognition step — identifying when a problem calls for topological sort — and the implementation steps of Kahn's algorithm. The dependency resolution algorithm pattern is consistent enough that spaced repetition locks it in quickly. Review the in-degree computation, queue initialization, and cycle check until they are automatic.