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).
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.
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.
Can you finish all courses given prerequisite pairs [course, prereq]?
Plan before you code
- Edges go prereq → course.
- Run Kahn's algorithm.
- Possible only if every course gets placed.
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
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}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}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}- Build the graph and count incoming edges.
- Start with everything that has no prerequisites.
- 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
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}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}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}Step by step
- Edges go prerequisite → course; count each course's prerequisites.
- Start with courses that need nothing.
- Take a course and unlock the courses waiting on it.
- Everything taken proves no cycle exists.
Complexity: O(V + E) time and space
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?
Kahn's algorithm or DFS?
Is the order unique?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
BFS by layers: each layer is one semester.
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
Course Schedule II
Return an order to take all courses, or an empty list if impossible.
- Same Kahn's algorithm as Course Schedule.
- Record the order nodes leave the queue.
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}Complexity: O(V + E) time and space
Alien Dictionary
Words are sorted in an unknown alphabet. Recover a valid letter order.
- Adjacent words reveal one edge: the first letters that differ.
- If a word is followed by its own prefix, the input is invalid.
- Topologically sort the letters.
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}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