Topological Sort

Linear ordering of vertices in a DAG — essential for dependency problems.

4 problems 0 Easy 4 Medium 0 Hard

Overview

Topological sort orders vertices so all edges point forward. It applies to any problem with dependencies: course scheduling, build systems, task ordering.

When to Use

Course Schedule (detect cycle)
Course Schedule II (ordering)
Alien dictionary
Minimum height trees
Parallel courses

Common Mistakes

Not detecting cycles before claiming a valid order exists
Using Kahn's algorithm vs DFS-based — both work, choose one
Bidirectional edges in a topological sort context

Complexity

Time

O(V + E)

Space

O(V)

// Kahn's Algorithm (BFS-based)
function topoSort(n, prerequisites) {
  const inDegree = new Array(n).fill(0);
  const adj = Array.from({length: n}, () => []);

  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    inDegree[a]++;
  }

  const queue = [];
  for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);

  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const nei of adj[node]) {
      if (--inDegree[nei] === 0) queue.push(nei);
    }
  }
  return order.length === n ? order : []; // empty = cycle exists
}

Problems (4)

Hide completed

Problem	Difficulty	Companies	Freq	Link
Course Schedule	Medium	AmazonFacebook +2	High
Course Schedule II	Medium	FacebookAmazon +1	High
Parallel Courses ★	Medium	AmazonGoogle	Medium	★
Sequence Reconstruction ★	Medium	GoogleSnapchat	Low	★

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee