Topological Sort Pattern

Why this pattern matters for LeetCode

Course Schedule is one of the most-asked medium problems in technical interviews. The question 'can you finish all courses?' is asking: does the prerequisite graph contain a cycle? If course A requires B which requires A, nothing can ever start. Topological sort solves this: try to produce an ordering where all prerequisites come before the courses that need them. If you can't, because a cycle prevents it, the ordering is impossible. The BFS version (Kahn's algorithm) makes this intuitive: start with everything that has no prerequisites, complete it, and unlock the next set.

What the Topological Sort pattern is

Topological sort produces a linear ordering of nodes in a directed graph such that for every directed edge u → v, node u comes before v. It only works on directed acyclic graphs (DAGs), any cycle makes ordering impossible. Kahn's algorithm counts incoming edges (in-degree) for every node. Start with all zero-in-degree nodes (no prerequisites). Process each one, decrement its neighbors' in-degrees, and add any newly zero-degree nodes to the queue. If you process all nodes, the graph was acyclic. If the queue empties before processing all nodes, a cycle exists.

Reach for Topological Sort when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Topological Sort

• ✓Course Schedule, can all courses be finished given the prerequisite graph?
• ✓Course Schedule II, return a valid order to take all courses
• ✓Alien Dictionary, infer character ordering from a sorted word list
• ✓Build system dependency resolution, compile A before B if B imports A
• ✓Minimum Height Trees, find the centroid using leaf-peeling (a topological sort variant)

When NOT to use Topological Sort

• ✕The graph is undirected, topological sort only applies to directed graphs
• ✕You need shortest paths, not ordering. Dijkstra or BFS applies
• ✕You just need to detect any path between two nodes, standard BFS/DFS without ordering is sufficient
• ✕The graph has cycles and you need to process them, use strongly connected components instead

Better alternative: In those cases, standard BFS/DFS (for reachability) or Dijkstra (for shortest paths) is more appropriate.

JavaScript code template

Course Schedule. Kahn's BFS, O(V + E) time and space

function canFinish(numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const adj = Array.from({ length: numCourses }, () => []);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course);  // prereq unlocks course
    inDegree[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i); // no prerequisites, start here
  }

  let completed = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    completed++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor); // newly unlocked
    }
  }

  return completed === numCourses; // false means a cycle trapped some nodes
}

Build an adjacency list and track in-degrees (number of incoming edges per node). Every course with in-degree 0 can start immediately. Process them one by one, decrementing the in-degree of every course they unlock. When a course's in-degree hits 0, it's available and joins the queue. Count every processed course. If the count equals numCourses, no cycle exists. If it doesn't, some courses were stuck in a cycle that never got unlocked.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Build an adjacency list: for each [course, prereq] pair, add course to adj[prereq] (prereq unlocks course).
2. 2Count in-degrees: for each [course, prereq] edge, increment inDegree[course].
3. 3Seed the queue with all nodes that have in-degree 0, these have no prerequisites.
4. 4Pop a node, increment a completed counter, and decrement the in-degree of all its neighbors.
5. 5If any neighbor's in-degree hits 0, push it onto the queue, it's now unlocked.
6. 6If completed equals numCourses, no cycle. If it's less, a cycle trapped some nodes.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Course Schedule

  Classic cycle detection, can you finish all courses given the prerequisite graph?

  Coming soon
• Course Schedule II

  Return the actual topological order instead of just checking if one exists.

  Coming soon
• Find if Path Exists in Graph

  BFS/DFS reachability check, a simpler graph problem that builds up to topological sort.

  Coming soon
• Alien Dictionary

  Infer character ordering from a sorted list of alien words, then topologically sort the character dependency graph.

  Coming soon

Common mistakes beginners make

• ✕Reversing the edge direction, the edge goes from prereq to course (prereq unlocks course), not course to prereq. Getting this backward flips which nodes have in-degree 0 at the start.
• ✕Not seeding the queue with all zero-in-degree nodes before starting, every node with no prerequisites must be in the initial queue, even if they're in separate components.
• ✕Using completed > 0 instead of completed === numCourses, you need all nodes processed, not just some.
• ✕Applying topological sort to an undirected graph, it's only defined for directed graphs where edges have a direction.

Topological Sort vs DFS Cycle Detection vs BFS

Choose the right tool for the job.

Time and space complexity

You visit each vertex once (O(V)) and process each edge once when decrementing in-degrees (O(E)). The adjacency list stores all edges and the in-degree array stores one value per vertex, both O(V + E) total space.

Frequently asked questions

What's the difference between Kahn's algorithm and DFS-based topological sort?

Both produce a valid topological ordering. Kahn's (BFS) iteratively removes nodes with no remaining prerequisites, making cycle detection a side effect of counting processed nodes. DFS-based sort uses a 'finished' timestamp to order nodes, nodes that finish DFS last go first in the output. Kahn's is usually easier to understand and debug for beginners.

Why can't you topologically sort a graph with cycles?

A topological ordering requires every edge to go from an earlier node to a later node. A cycle means node A must come before B which must come before A, a contradiction. No valid linear ordering exists. In Kahn's algorithm, nodes in a cycle never reach in-degree 0, so the queue empties before all nodes are processed.

When is topological sort useful outside of course schedules?

Any time you have dependencies: build systems (compile A before B if B imports A), package managers (install dependencies before the package), spreadsheet formula evaluation (evaluate referenced cells before referencing cells), and task schedulers with ordering constraints.

Can I use topological sort for undirected graphs?

No. Topological sort is defined for directed graphs, edges have a direction that establishes 'before and after.' An undirected graph doesn't have this. For undirected connectivity questions, use standard BFS/DFS or Union Find instead.