Topological sort pattern

Order tasks so every dependency comes first.

Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

Count incoming edges. Start with nodes that have none, remove them and decrement their neighbours. Unplaced nodes mean a cycle (Kahn's algorithm).

Why it works

A node with no remaining prerequisites can safely go next. Kahn's algorithm keeps taking such nodes and removing their outgoing edges, which may free more nodes. Any node that never reaches zero prerequisites is stuck in, or behind, a cycle.

Typical cost: O(V + E) time and space

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Prerequisites, build order, dependenciesDetect a cycle in a directed graphAlien dictionary ordering
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Course Schedule

The problem statement, then the plan you would say out loud.

Problem

Can you finish all courses given prerequisite pairs [course, prereq]?

Plan before you code

  1. Edges go prereq → course.
  2. Run Kahn's algorithm.
  3. Possible only if every course gets placed.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

Kahn's algorithm

TypeScriptKotlinJava
kahns-algorithm.tsTypeScriptCopy
1// edge [a, b]: a must come before b2function topoOrder(n: number, edges: [number, number][]): number[] {3  const graph: number[][] = Array.from({ length: n }, () => []);4  const indeg = new Array<number>(n).fill(0);5  for (const [a, b] of edges) {6    graph[a].push(b);7    indeg[b]++;8  }9  const q = [...indeg.keys()].filter((i) => indeg[i] === 0);10  for (let head = 0; head < q.length; head++) {11    for (const next of graph[q[head]]) {12      if (--indeg[next] === 0) q.push(next);13    }14  }15  return q.length === n ? q : [];   // [] means a cycle16}
16 linesUTF-8TypeScript
kahns-algorithm.ktKotlinCopy
1// edge (a, b): a must come before b2fun topoOrder(n: Int, edges: List<Pair<Int, Int>>): List<Int> {3    val graph = List(n) { mutableListOf<Int>() }4    val indeg = IntArray(n)5    for ((a, b) in edges) {6        graph[a].add(b)7        indeg[b]++8    }9    val q = (0 until n).filter { indeg[it] == 0 }.toMutableList()10    var head = 011    while (head < q.size) {12        for (next in graph[q[head++]]) {13            if (--indeg[next] == 0) q.add(next)14        }15    }16    return if (q.size == n) q else emptyList()   // empty means a cycle17}
17 linesUTF-8Kotlin
kahns-algorithm.javaJavaCopy
1// edge {a, b}: a must come before b2static List<Integer> topoOrder(int n, int[][] edges) {3  List<List<Integer>> graph = new ArrayList<>();4  for (int i = 0; i < n; i++) graph.add(new ArrayList<>());5  int[] indeg = new int[n];6  for (int[] e : edges) {7    graph.get(e[0]).add(e[1]);8    indeg[e[1]]++;9  }10  List<Integer> q = new ArrayList<>();11  for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);12  for (int head = 0; head < q.size(); head++) {13    for (int next : graph.get(q.get(head))) {14      if (--indeg[next] == 0) q.add(next);15    }16  }17  return q.size() == n ? q : List.of();   // empty means a cycle18}
18 linesUTF-8Java
  1. Build the graph and count incoming edges.
  2. Start with everything that has no prerequisites.
  3. Removing a node may free its neighbours. The queue, read in order, is the answer.

3.2Solution

Strict TypeScript, type-checked and tested.

Course Schedule

TypeScriptKotlinJava
course-schedule.tsTypeScriptCopy
1function canFinish(n: number, prereqs: [number, number][]): boolean {2  const graph: number[][] = Array.from({ length: n }, () => []);3  const indeg = new Array<number>(n).fill(0);4  for (const [course, pre] of prereqs) {5    graph[pre].push(course);6    indeg[course]++;7  }8  const q = [...indeg.keys()].filter((i) => indeg[i] === 0);9  let taken = 0;10  for (let head = 0; head < q.length; head++) {11    taken++;12    for (const next of graph[q[head]]) {13      if (--indeg[next] === 0) q.push(next);14    }15  }16  return taken === n;17}
17 linesUTF-8TypeScript
course-schedule.ktKotlinCopy
1fun canFinish(n: Int, prereqs: List<Pair<Int, Int>>): Boolean {2    val graph = List(n) { mutableListOf<Int>() }3    val indeg = IntArray(n)4    for ((course, pre) in prereqs) {5        graph[pre].add(course)6        indeg[course]++7    }8    val q = (0 until n).filter { indeg[it] == 0 }.toMutableList()9    var taken = 010    var head = 011    while (head < q.size) {12        taken++13        for (next in graph[q[head++]]) {14            if (--indeg[next] == 0) q.add(next)15        }16    }17    return taken == n18}
18 linesUTF-8Kotlin
course-schedule.javaJavaCopy
1static boolean canFinish(int n, int[][] prereqs) {2  List<List<Integer>> graph = new ArrayList<>();3  for (int i = 0; i < n; i++) graph.add(new ArrayList<>());4  int[] indeg = new int[n];5  for (int[] p : prereqs) {   // p = {course, pre}6    graph.get(p[1]).add(p[0]);7    indeg[p[0]]++;8  }9  List<Integer> q = new ArrayList<>();10  for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);11  int taken = 0;12  for (int head = 0; head < q.size(); head++) {13    taken++;14    for (int next : graph.get(q.get(head))) {15      if (--indeg[next] == 0) q.add(next);16    }17  }18  return taken == n;19}
19 linesUTF-8Java

Step by step

  1. Edges go prerequisite → course; count each course's prerequisites.
  2. Start with courses that need nothing.
  3. Take a course and unlock the courses waiting on it.
  4. Everything taken proves no cycle exists.

Complexity: O(V + E) time and space

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

How do you detect a cycle?
If the order has fewer nodes than the graph, the missing nodes are in a cycle or depend on one.
Kahn's algorithm or DFS?
Kahn's gives cycle detection and a natural order for free; reversed DFS post-order also works and is handy when you are already doing DFS.
Is the order unique?
Only if exactly one node is ready at every step. Otherwise many valid orders exist.

4.2Solo practice

Try these without looking; open the hint only when stuck.

MediumParallel Courses
Hint

BFS by layers: each layer is one semester.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Course Schedule II

Return an order to take all courses, or an empty list if impossible.

  1. Same Kahn's algorithm as Course Schedule.
  2. Record the order nodes leave the queue.
course-schedule-ii.tsTypeScriptCopy
1function findOrder(n: number, prereqs: [number, number][]): number[] {2  const graph: number[][] = Array.from({ length: n }, () => []);3  const indeg = new Array<number>(n).fill(0);4  for (const [course, pre] of prereqs) {5    graph[pre].push(course);6    indeg[course]++;7  }8  const order = [...indeg.keys()].filter((i) => indeg[i] === 0);9  for (let head = 0; head < order.length; head++) {10    for (const next of graph[order[head]]) {11      if (--indeg[next] === 0) order.push(next);12    }13  }14  return order.length === n ? order : [];15}
15 linesUTF-8TypeScript

Complexity: O(V + E) time and space

Hard

Alien Dictionary

Words are sorted in an unknown alphabet. Recover a valid letter order.

  1. Adjacent words reveal one edge: the first letters that differ.
  2. If a word is followed by its own prefix, the input is invalid.
  3. Topologically sort the letters.
alien-dictionary.tsTypeScriptCopy
1function alienOrder(words: string[]): string {2  const graph = new Map<string, Set<string>>();3  const indeg = new Map<string, number>();4  for (const ch of words.join("")) {5    if (!graph.has(ch)) graph.set(ch, new Set());6    indeg.set(ch, 0);7  }8  for (let k = 0; k + 1 < words.length; k++) {9    const a = words[k], b = words[k + 1];10    let j = 0;11    while (j < a.length && j < b.length && a[j] === b[j]) j++;12    if (j === Math.min(a.length, b.length)) {13      if (a.length > b.length) return "";   // "abc" before "ab" is invalid14      continue;15    }16    if (!graph.get(a[j])!.has(b[j])) {17      graph.get(a[j])!.add(b[j]);18      indeg.set(b[j], indeg.get(b[j])! + 1);19    }20  }21  const order = [...graph.keys()].filter((ch) => indeg.get(ch) === 0);22  for (let head = 0; head < order.length; head++) {23    for (const next of graph.get(order[head])!) {24      indeg.set(next, indeg.get(next)! - 1);25      if (indeg.get(next) === 0) order.push(next);26    }27  }28  return order.length === graph.size ? order.join("") : "";29}
29 linesUTF-8TypeScript

Complexity: O(total characters) time

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Reversing edge direction
  • Forgetting nodes with no edges at all