Algorithms & Coding Interviews · Graphs

Topological Sort

Topological sort orders tasks so every prerequisite comes first, and detects impossible (cyclic) dependencies. Learn Kahn's algorithm with in-degrees, three-colour DFS cycle detection, when to use each, and watch a course schedule resolved and a cycle caught step by step.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 11 min read▶ 2 interactive🛠️ 4 exercises

🎯 What you'll learn

DAGs, dependencies and topological order
Kahn's algorithm and BFS levels
Three-colour DFS and back edges
Six LeetCode problems up to Alien Dictionary

📚 Before you start

Graph BFS, DFS & grids

Part 1The Pattern

A topological order lists the nodes of a directed acyclic graph (DAG) so that every edge points forward: each task appears after all of its prerequisites. Build systems, package managers, course schedules, spreadsheet recalculation and database migrations all rely on it. Two algorithms produce one in O(V + E): Kahn's algorithm (repeatedly take a node with no remaining prerequisites) and DFS postorder (finish a node after all its descendants, then reverse). Both also detect cycles, which is often the real question.

Kahn's algorithm removing nodes with in-degree zero

1Recognition Cues

"prerequisites", "dependencies", "must happen before", "build order"
"is it possible to finish all tasks?" (= is the dependency graph acyclic?)
"order of letters in an alien language" (derive edges from adjacent sorted words)
"minimum number of semesters/rounds" (BFS levels of Kahn's algorithm)

2Kahn's Algorithm (BFS)

typescript

function topoOrder(n: number, edges: number[][]): number[] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [a, b] of edges) { adj[a].push(b); indeg[b]++; }
  const q: number[] = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  for (let head = 0; head < q.length; head++) {
    const u = q[head];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return order.length === n ? order : [];
}

python

from collections import deque

def topo_order(n, edges):                   # edges: (a, b) means a must come before b
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:
        adj[a].append(b)
        indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:               # all prerequisites done
                q.append(v)
    return order if len(order) == n else [] # leftover nodes → a cycle

In-degree = number of unfinished prerequisites. Nodes with in-degree 0 can be done now; finishing one decrements its dependents. If the queue empties before every node is output, the remaining nodes all wait on each other: a cycle.

3DFS with Three Colours

text

WHITE = unvisited, GRAY = on the current DFS path, BLACK = finished
dfs(u): color[u] = GRAY
        for v in adj[u]: if GRAY → cycle!  if WHITE → dfs(v)
        color[u] = BLACK; order.append(u)
topological order = reversed(order)

A back edge to a GRAY node means the path loops back on itself. Two colours (visited / not) are not enough for directed graphs: reaching a BLACK node through another path is fine.

4Kahn vs DFS

	Kahn (BFS)	DFS postorder
cycle detection	`len(order) < n`	back edge to a GRAY node
natural extras	levels (parallel rounds), lexicographically smallest order with a heap	finishing times, recursion-friendly
recursion depth issues	none	deep chains can overflow the stack

Under the HoodWhere You've Seen It▾

npm/pip install dependencies in topological order; make and Bazel build targets that way; Terraform builds a resource graph and applies it in dependency order (in parallel by levels); Excel recalculates cells topologically and reports circular references, which is exactly Kahn's leftover-node check.

⚠️ Common Pitfalls

Edge direction mix-ups: [course, prereq] usually means prereq → course. Read the statement twice.
Undirected cycle checks on directed graphs: need the three-colour scheme (or Kahn's count).
Forgetting isolated nodes (in-degree 0, no edges) in the output.
Alien Dictionary edge cases: a longer word before its own prefix ("abc" before "ab") is invalid.
Assuming a unique order: most DAGs have many valid topological orders; verify by checking edges, not by comparing with one expected list.

📋 Quick Reference

text

Kahn: indeg; queue all indeg==0; pop u → output; for v: indeg[v]--, push if 0
cycle ⇔ output size < n
DFS: WHITE/GRAY/BLACK; GRAY neighbour = cycle; append on finish; reverse
O(V + E) time and space

Part 2Interview Problems

Six problems: feasibility and ordering of course schedules, deriving edges for an alien alphabet, peeling leaves, levels as semesters, and three-colour cycle detection.

1Course Schedule (LeetCode 207)

🟠 Medium. prerequisites[i] = [a, b] means course b must be taken before a. Can all numCourses be finished?

text

numCourses = 2, [[1,0],[0,1]] → false (cycle)

Approach. Build edges b → a, run Kahn's algorithm, and check that every course was output (no cycle).

Complexity. O(V + E) time and space.

typescript

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  for (let head = 0; head < q.length; head++) {
    taken++;
    for (const v of adj[q[head]]) if (--indeg[v] === 0) q.push(v);
  }
  return taken === numCourses;
}

python

from collections import deque

def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(num_courses) if indeg[i] == 0)
    taken = 0
    while q:
        u = q.popleft()
        taken += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return taken == num_courses

2Course Schedule II (LeetCode 210)

🟠 Medium. Return any order in which all courses can be taken, or [] if impossible.

text

4, [[1,0],[2,0],[3,1],[3,2]] → [0,1,2,3] or [0,2,1,3]

Approach. Same as Course Schedule, but record the order in which Kahn's algorithm outputs courses.

Complexity. O(V + E).

typescript

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const order: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) order.push(i);
  for (let head = 0; head < order.length; head++)
    for (const v of adj[order[head]]) if (--indeg[v] === 0) order.push(v);
  return order.length === numCourses ? order : [];
}

python

from collections import deque

def find_order(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(num_courses) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == num_courses else []

3Alien Dictionary (LeetCode 269)

🔴 Hard. Words are sorted in an unknown alphabet. Return a valid letter order, or "" if the input is inconsistent.

text

["wrt","wrf","er","ett","rftt"] → "wertf"

Approach. Compare each pair of adjacent words: the first differing letters give an edge a → b. If a word is followed by its own proper prefix ("abc", "ab"), the input is invalid. Topologically sort all letters that appear; a cycle means "".

Complexity. O(C) for C total characters (alphabet is small).

typescript

function alienOrder(words: string[]): string {
  const adj = new Map<string, Set<string>>(), indeg = new Map<string, number>();
  for (const w of words) for (const c of w) { if (!adj.has(c)) { adj.set(c, new Set()); indeg.set(c, 0); } }
  for (let i = 0; i + 1 < words.length; i++) {
    const w1 = words[i], w2 = words[i + 1];
    let found = false;
    for (let k = 0; k < Math.min(w1.length, w2.length); k++) {
      if (w1[k] !== w2[k]) {
        if (!adj.get(w1[k])!.has(w2[k])) { adj.get(w1[k])!.add(w2[k]); indeg.set(w2[k], indeg.get(w2[k])! + 1); }
        found = true;
        break;
      }
    }
    if (!found && w1.length > w2.length) return "";
  }
  const q = [...indeg.keys()].filter((c) => indeg.get(c) === 0).sort();
  const out: string[] = [];
  for (let head = 0; head < q.length; head++) {
    const c = q[head];
    out.push(c);
    for (const d of [...adj.get(c)!].sort()) {
      indeg.set(d, indeg.get(d)! - 1);
      if (indeg.get(d) === 0) q.push(d);
    }
  }
  return out.length === indeg.size ? out.join("") : "";
}

python

from collections import deque

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for w1, w2 in zip(words, words[1:]):
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:
                    adj[a].add(b)
                    indeg[b] += 1
                break
        else:
            if len(w1) > len(w2):
                return ""                      # "abc" before "ab" is impossible
    q = deque(sorted(c for c in indeg if indeg[c] == 0))
    out = []
    while q:
        c = q.popleft()
        out.append(c)
        for d in sorted(adj[c]):
            indeg[d] -= 1
            if indeg[d] == 0:
                q.append(d)
    return "".join(out) if len(out) == len(indeg) else ""

4Minimum Height Trees (LeetCode 310)

🟠 Medium. In an undirected tree of n nodes, return all roots that minimise the tree's height.

text

n = 6, edges [[3,0],[3,1],[3,2],[3,4],[5,4]] → [3,4]

Approach. Peel leaves layer by layer (Kahn's algorithm on an undirected tree, using degree instead of in-degree). The last one or two nodes remaining are the centres of the longest path: the roots of minimum height.

Complexity. O(n) time.

typescript

function findMinHeightTrees(n: number, edges: number[][]): number[] {
  if (n <= 2) return [...Array(n).keys()];
  const adj: Set<number>[] = Array.from({ length: n }, () => new Set());
  for (const [a, b] of edges) { adj[a].add(b); adj[b].add(a); }
  let leaves = [...Array(n).keys()].filter((i) => adj[i].size === 1);
  let remaining = n;
  while (remaining > 2) {
    remaining -= leaves.length;
    const next: number[] = [];
    for (const leaf of leaves) {
      const nb = adj[leaf].values().next().value!;
      adj[nb].delete(leaf);
      if (adj[nb].size === 1) next.push(nb);
    }
    leaves = next;
  }
  return leaves;
}

python

def find_min_height_trees(n, edges):
    if n <= 2:
        return list(range(n))
    adj = [set() for _ in range(n)]
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    leaves = [i for i in range(n) if len(adj[i]) == 1]
    remaining = n
    while remaining > 2:
        remaining -= len(leaves)
        new_leaves = []
        for leaf in leaves:
            nb = adj[leaf].pop()
            adj[nb].remove(leaf)
            if len(adj[nb]) == 1:
                new_leaves.append(nb)
        leaves = new_leaves
    return leaves

5Parallel Courses (LeetCode 1136)

🟠 Medium. Courses 1..n with relations[i] = [prev, next]. Each semester you may take any number of courses whose prerequisites are done. Return the minimum number of semesters, or −1 if impossible.

text

n = 3, [[1,3],[2,3]] → 2

Approach. Kahn's algorithm by levels: each BFS level is one semester. If not all courses get taken, there's a cycle.

Complexity. O(V + E).

typescript

function minimumSemesters(n: number, relations: number[][]): number {
  const adj: number[][] = Array.from({ length: n + 1 }, () => []);
  const indeg = new Array(n + 1).fill(0);
  for (const [a, b] of relations) { adj[a].push(b); indeg[b]++; }
  let level: number[] = [];
  for (let i = 1; i <= n; i++) if (indeg[i] === 0) level.push(i);
  let semesters = 0, taken = 0;
  while (level.length) {
    semesters++;
    taken += level.length;
    const next: number[] = [];
    for (const u of level) for (const v of adj[u]) if (--indeg[v] === 0) next.push(v);
    level = next;
  }
  return taken === n ? semesters : -1;
}

python

def minimum_semesters(n, relations):
    adj = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for a, b in relations:
        adj[a].append(b)
        indeg[b] += 1
    level = [i for i in range(1, n + 1) if indeg[i] == 0]
    semesters = taken = 0
    while level:
        semesters += 1
        taken += len(level)
        nxt = []
        for u in level:
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    nxt.append(v)
        level = nxt
    return semesters if taken == n else -1

6Find Eventual Safe States (LeetCode 802)

🟠 Medium. A node is safe if every path from it ends at a terminal node (no outgoing edges). Return all safe nodes in ascending order.

text

[[1,2],[2,3],[5],[0],[5],[],[]] → [2,4,5,6]

Approach. Three-colour DFS: a node is unsafe if it reaches a GRAY node (cycle) or any unsafe node. Memoise results (BLACK = safe). Equivalently, run Kahn's algorithm on the reversed graph starting from terminal nodes.

Complexity. O(V + E).

typescript

function eventualSafeNodes(graph: number[][]): number[] {
  const color = new Array(graph.length).fill(0);   // 0 white, 1 gray, 2 black
  const safe = (u: number): boolean => {
    if (color[u] !== 0) return color[u] === 2;
    color[u] = 1;
    for (const v of graph[u]) if (!safe(v)) return false;
    color[u] = 2;
    return true;
  };
  return graph.map((_, u) => u).filter((u) => safe(u));
}

python

def eventual_safe_nodes(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(graph)

    def safe(u):
        if color[u] != WHITE:
            return color[u] == BLACK
        color[u] = GRAY
        for v in graph[u]:
            if not safe(v):
                return False                  # stays GRAY → unsafe
        color[u] = BLACK
        return True

    return [u for u in range(len(graph)) if safe(u)]

🧠 Key takeaways

Topological order exists only for DAGs; both algorithms run in O(V + E).
Kahn: queue nodes with in-degree 0; leftover nodes ⇒ cycle; levels = parallel rounds.
DFS: WHITE/GRAY/BLACK; an edge to a GRAY node is a back edge (cycle).
Check edge direction carefully; many valid orders usually exist.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_topological_sort_exercise_1.py

TS PY

algo_topological_sort_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Kahn's algorithm outputs 4 of 6 nodes. What does that mean?

Nobody can start.

2. In three-colour DFS, reaching a BLACK node means…

Only GRAY means a cycle.

3. Minimum number of semesters for a course DAG equals…

Each level is a semester.

4. For [course, prereq] pairs, the edge direction is…

Prerequisite first.

Source: algo_topological_sort_theory_1.md, algo_topological_sort_theory_2.md · generated by tools/build_lessons.py