These are the notes for DSA episode 51. Some subjects need others first: in what order can you take them all, or is it impossible? When a directed graph has no cycle, we can list its vertices so that every arrow points forward. That list is a topological order. We start from a real-life problem (planning engineering subjects), define every word, try the obvious brute force (rescan for a ready course, again and again) that hits Time Limit Exceeded on a 1 lakh-course chain, find the key insight (count each course's pending prerequisites, its in-degree; 0 means ready, and taking a course only changes the courses that need it), and finish with Kahn's algorithm in O(V + E), which also detects cycles. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
You've just joined engineering, and you must plan all your subjects. Some subjects need others first: Data Structures needs Programming; Algorithms needs Data Structures and Maths. You need an order where every subject comes after everything it needs. And if the rules say A needs B and B needs A, no order exists: the plan is impossible.
| In college | In the graph |
|---|---|
| A subject | a vertex (a course) |
| "Take Programming before Data Structures" | an arrow Programming → Data Structures |
| The number of pending prerequisites of a subject | its in-degree |
| Subjects you may take right now | vertices with in-degree 0, waiting in a queue |
| Passing a subject | removing its arrows: each dependent's in-degree drops by 1 |
| A semester plan where everything fits | a topological order |
| "A needs B and B needs A" | a cycle: no order exists |
Every word, from zero
- Prerequisite: a course you must finish before another. Dependency: the other way round: Data Structures depends on Programming.
- Directed edge (arrow)
b → a: "takebbeforea". We draw it from the prerequisite to the course that needs it. - DAG (directed acyclic graph): a directed graph with no cycle. Only DAGs have a topological order.
- Topological order (topological sort): a list of all vertices where every arrow goes from an earlier vertex to a later one. A DAG can have many valid orders.
- In-degree: the number of arrows coming into a vertex. Here: how many prerequisites are still pending.
- Out-degree: the number of arrows going out.
- Queue: first in, first out (
ArrayDeque:add,poll). - Kahn's algorithm: repeatedly take a vertex with in-degree 0, append it to the order, and remove its outgoing arrows. Published by A. B. Kahn in 1962.
- Level (of Kahn's algorithm): all the courses that become ready at the same time; one semester in practice 1.
Problem statement
LeetCode 207, Course Schedule: there are numCourses courses 0..n-1. prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses.
LeetCode 210, Course Schedule II: same input; return one valid order, or an empty array if it is impossible.
| n | prerequisites | 210 answer | 207 answer |
|---|---|---|---|
| 2 | [1,0] |
[0, 1] |
true |
| 2 | [1,0], [0,1] |
[] |
false |
| 4 | [1,0], [2,0], [3,1], [3,2] |
[0, 1, 2, 3] (also [0, 2, 1, 3]) |
true |
Careful: in [a, b] the prerequisite is the second number. LeetCode allows up to 2,000 courses; we also test 1 lakh.
Brute force: look for a ready course, again and again
The way you'd do it on paper: scan the courses for one not taken yet whose prerequisites are all done (check every pair), take it, write it down, repeat n times. If no course is ready but some are left, they're waiting for each other: return [].
import java.util.*;
public class Main {
static int[] findOrder(int n, int[][] pre) {
boolean[] done = new boolean[n];
int[] order = new int[n];
for (int k = 0; k < n; k++) {
int pick = -1;
for (int c = 0; c < n && pick == -1; c++) {
if (done[c]) continue;
boolean ready = true;
for (int[] p : pre)
if (p[0] == c && !done[p[1]]) { ready = false; break; }
if (ready) pick = c;
}
if (pick == -1) return new int[0];
done[pick] = true; order[k] = pick;
}
return order;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}})));
System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}})));
}
}
[0, 1]
[0, 1, 2, 3]
[]
A 1 lakh-course chain: Time Limit Exceeded
Course 0 needs 1, 1 needs 2, and so on, so course 99999 must come first.
int n = 100000;
int[][] pre = new int[n - 1][];
for (int i = 0; i + 1 < n; i++) pre[i] = new int[]{i, i + 1};
long t0 = System.nanoTime();
int[] order = findOrder(n, pre);
System.out.println(order.length + " courses, first " + order[0] + ", "
+ (System.nanoTime() - t0) / 1000000 + " ms");
(no output: Time Limit Exceeded after 8 seconds)
Why it is slow
n picks × a scan of up to n courses × a check of all E pairs: O(n × n × E). And it's wasteful: after every pick we ask every course again, "are you ready now?", although finishing one course can only change the answer for the courses that need it.
The key insight: count the pending prerequisites
| On a checklist | In code |
|---|---|
| "Pending prerequisites: 2" written on each subject | indeg[c]: arrows coming in |
| Pending 0: you may take it now | courses with indeg == 0 go into a queue |
| Pass a subject, tell only the ones that need it | for each arrow c → d: indeg[d]-- |
| A subject's number hits 0 | it joins the queue |
Walkthrough on example 3 (0 → 1, 0 → 2, 1 → 3, 2 → 3):
in-degree: 0:0 1:1 2:1 3:2 queue [0]
take 0 → 1:0 2:0 3:2 queue [1, 2] order 0
take 1 → 3:1 queue [2] order 0 1
take 2 → 3:0 queue [3] order 0 1 2
take 3 queue [] order 0 1 2 3 (4 of 4: possible)
And a cycle? 2 → 0, 0 → 1, 1 → 2: every course has in-degree 1, nobody is ever ready, the queue is empty from the start, and we take 0 of 3 courses. Taking fewer than n courses means there is a cycle. So Kahn's algorithm also detects cycles, with no recursion at all.
Steps:
- For every pair
[a, b]: arrowb → a,indeg[a]++. - Every course with
indeg == 0goes into the queue. - Poll
c, append it to the order. - For each arrow
c → d:indeg[d]--; if it becomes 0, addd. - Took all
n? Return the order; otherwise return[](a cycle).
The optimal solution in Java: Kahn's algorithm
import java.util.*;
public class Main {
static int[] findOrder(int n, int[][] pre) {
List<List<Integer>> next = new ArrayList<>();
for (int c = 0; c < n; c++) next.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int c = q.poll();
order[k++] = c;
for (int d : next.get(c))
if (--indeg[d] == 0) q.add(d);
}
return k == n ? order : new int[0];
}
static boolean canFinish(int n, int[][] pre) {
return findOrder(n, pre).length == n;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}})));
System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}})));
System.out.println(Arrays.toString(findOrder(3, new int[][]{})));
System.out.println(Arrays.toString(findOrder(3, new int[][]{{0, 1}, {1, 2}, {2, 0}})));
System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
}
}
[0, 1]
[0, 1, 2, 3]
[]
[0, 1, 2]
[]
false
The three examples; then 3 courses with no prerequisites ([0, 1, 2]), a 3-course cycle ([]), and canFinish on the impossible pair (false).
The 1 lakh chain:
100000 courses, first 99999, 60 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
vector<int> findOrder(int n, const vector<pair<int, int>>& pre) { // pair {a, b}: take b before a
vector<vector<int>> next(n);
vector<int> indeg(n, 0);
for (auto [a, b] : pre) { next[b].push_back(a); indeg[a]++; }
queue<int> q;
for (int c = 0; c < n; c++) if (indeg[c] == 0) q.push(c);
vector<int> order;
while (!q.empty()) {
int c = q.front(); q.pop();
order.push_back(c);
for (int d : next[c])
if (--indeg[d] == 0) q.push(d);
}
if ((int)order.size() < n) return {}; // a cycle: impossible
return order;
}
bool canFinish(int n, const vector<pair<int, int>>& pre) { return (int)findOrder(n, pre).size() == n; }
void show(const vector<int>& v) {
cout << "[";
for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
cout << "]\n";
}
int main() {
show(findOrder(2, {{1, 0}})); // [0, 1]
show(findOrder(4, {{1, 0}, {2, 0}, {3, 1}, {3, 2}})); // [0, 1, 2, 3]
show(findOrder(2, {{1, 0}, {0, 1}})); // []
cout << boolalpha << canFinish(2, {{1, 0}, {0, 1}}) << "\n"; // false
}
[0, 1]
[0, 1, 2, 3]
[]
false
The same solution in Python
from collections import deque
def find_order(n, pre): # [a, b]: take b before a
nxt = [[] for _ in range(n)]
indeg = [0] * n
for a, b in pre:
nxt[b].append(a)
indeg[a] += 1
q = deque(c for c in range(n) if indeg[c] == 0)
order = []
while q:
c = q.popleft()
order.append(c)
for d in nxt[c]:
indeg[d] -= 1
if indeg[d] == 0:
q.append(d)
return order if len(order) == n else []
def can_finish(n, pre):
return len(find_order(n, pre)) == n
print(find_order(2, [[1, 0]])) # [0, 1]
print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])) # [0, 1, 2, 3]
print(find_order(2, [[1, 0], [0, 1]])) # []
print(can_finish(2, [[1, 0], [0, 1]])) # False
[0, 1]
[0, 1, 2, 3]
[]
False
The other way: DFS (episode 50)
A three-colour DFS also gives a topological order: when a vertex turns black, append it to a list; the reverse of that list is a topological order (a vertex is finished only after everything it points to). An arrow to a grey vertex means a cycle. Kahn's algorithm is usually preferred in interviews: no recursion, and the cycle check is a simple count.
Three real bugs
Bug 1: drawing the arrow backwards
import java.util.*;
public class Main {
static int[] findOrder(int n, int[][] pre) {
List<List<Integer>> next = new ArrayList<>();
for (int c = 0; c < n; c++) next.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : pre) { next.get(p[0]).add(p[1]); indeg[p[1]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int c = q.poll();
order[k++] = c;
for (int d : next.get(c))
if (--indeg[d] == 0) q.add(d);
}
return k == n ? order : new int[0];
}
public static void main(String[] args) {
System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
}
}
[3, 1, 2, 0]
[3, 1, 2, 0]: every course before its prerequisites. In a pair [a, b], b comes first: the arrow goes from b to a.
Bug 2: no check that all n courses were taken
import java.util.*;
public class Main {
static int[] findOrder(int n, int[][] pre) {
List<List<Integer>> next = new ArrayList<>();
for (int c = 0; c < n; c++) next.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int c = q.poll();
order[k++] = c;
for (int d : next.get(c))
if (--indeg[d] == 0) q.add(d);
}
return order;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(findOrder(3, new int[][]{{1, 0}, {2, 1}, {1, 2}})));
}
}
[0, 0, 0]
[0, 0, 0]. Courses 1 and 2 need each other, so only course 0 was taken; the rest of the array is Java's default zeros. It looks like an answer but it's garbage. Always compare k with n.
Bug 3: adding a course every time its count drops
import java.util.*;
public class Main {
static int[] findOrder(int n, int[][] pre) {
List<List<Integer>> next = new ArrayList<>();
for (int c = 0; c < n; c++) next.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int c = 0; c < n; c++) if (indeg[c] == 0) q.add(c);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int c = q.poll();
order[k++] = c;
for (int d : next.get(c))
{ indeg[d]--; q.add(d); }
}
return k == n ? order : new int[0];
}
public static void main(String[] args) {
System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
at Main.findOrder(Main.java:15)
at Main.main(Main.java:22)
Course 3 went into the queue twice (once for each prerequisite), so we tried to write a fifth course into an array of four. And the first time, course 2 wasn't done yet. A course is ready only when its count is exactly 0.
Complexity
| Approach | Time | Space | 1 lakh chain |
|---|---|---|---|
| Rescan for a ready course | O(n × n × E) | O(n) | Time Limit Exceeded |
| Kahn's algorithm | O(V + E) | O(V + E) | milliseconds |
| DFS, reverse finishing order | O(V + E) | O(V + E) | (use an iterative DFS for deep chains) |
Kahn's algorithm puts each course in the queue once and crosses out each arrow once.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
Arrow a → b for pair [a, b] |
[3, 1, 2, 0] |
every rule broken | arrow b → a, indeg[a]++ |
No k == n check |
[0, 0, 0] |
a cycle stops the queue early | k == n ? order : new int[0] |
Add d whenever indeg drops |
ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4 |
d queued twice, too early |
add only when it reaches 0 |
| Rescanning for a ready course | Time Limit Exceeded | O(n × n × E) | in-degree + queue |
| Expecting one exact order | "wrong answer" on your own tests | many orders are valid | check that every arrow points forward |
Mini project: the semester planner
Subjects with prerequisites in, subjects per semester out. Kahn's algorithm level by level (freeze q.size(), exactly like the minutes of rotting oranges) gives the minimum number of semesters when any number of subjects fit in one semester.
import java.util.*;
public class Main {
// Mini project: a semester planner. Subjects with prerequisites -> subjects per semester (Kahn level by level).
public static void main(String[] args) {
String[] subj = {"Programming", "Maths", "Data Structures", "Databases", "Algorithms", "Operating Systems", "Compilers"};
String[][] needs = {{"Data Structures", "Programming"}, {"Databases", "Programming"}, {"Algorithms", "Data Structures"},
{"Algorithms", "Maths"}, {"Operating Systems", "Data Structures"}, {"Compilers", "Algorithms"},
{"Compilers", "Operating Systems"}};
Map<String, Integer> id = new HashMap<>();
for (int i = 0; i < subj.length; i++) id.put(subj[i], i);
int n = subj.length;
List<List<Integer>> next = new ArrayList<>();
for (int i = 0; i < n; i++) next.add(new ArrayList<>());
int[] indeg = new int[n];
for (String[] p : needs) { next.get(id.get(p[1])).add(id.get(p[0])); indeg[id.get(p[0])]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
int sem = 0, taken = 0;
while (!q.isEmpty()) {
sem++;
List<String> now = new ArrayList<>();
for (int size = q.size(); size > 0; size--) {
int c = q.poll(); now.add(subj[c]); taken++;
for (int d : next.get(c)) if (--indeg[d] == 0) q.add(d);
}
System.out.println("Semester " + sem + ": " + String.join(", ", now));
}
System.out.println(taken == n ? "All " + n + " subjects planned" : "Impossible: a cycle of prerequisites");
}
}
Semester 1: Programming, Maths
Semester 2: Data Structures, Databases
Semester 3: Algorithms, Operating Systems
Semester 4: Compilers
All 7 subjects planned
Practice
1. Parallel Courses (LeetCode 1136). Courses 1..n, relations[i] = [prev, next]. In one semester you may take any number of courses whose prerequisites are done. Minimum number of semesters, or -1.
Solution
import java.util.*;
public class Main {
// Parallel Courses (LeetCode 1136): courses 1..n, relation {prev, next}; any number of courses per semester.
// Minimum semesters = the number of Kahn LEVELS (like the minutes in rotting oranges). -1 if there is a cycle.
static int minimumSemesters(int n, int[][] relations) {
List<List<Integer>> next = new ArrayList<>();
for (int c = 0; c <= n; c++) next.add(new ArrayList<>());
int[] indeg = new int[n + 1];
for (int[] r : relations) { next.get(r[0]).add(r[1]); indeg[r[1]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int c = 1; c <= n; c++) if (indeg[c] == 0) q.add(c);
int semesters = 0, taken = 0;
while (!q.isEmpty()) {
semesters++;
for (int size = q.size(); size > 0; size--) {
int c = q.poll(); taken++;
for (int d : next.get(c)) if (--indeg[d] == 0) q.add(d);
}
}
return taken == n ? semesters : -1;
}
public static void main(String[] args) {
System.out.println(minimumSemesters(3, new int[][]{{1, 3}, {2, 3}}));
System.out.println(minimumSemesters(3, new int[][]{{1, 2}, {2, 3}, {3, 1}}));
}
}
2
-1
2. Alien Dictionary. Words are sorted in an unknown alphabet. Find one valid order of the letters (empty if impossible).
Solution
Compare neighbouring words: the first position where they differ gives an arrow (the first word's letter comes before the second's). Then Kahn's algorithm on the letters. A word followed by its own prefix ("abc" before "ab") is impossible.
import java.util.*;
public class Main {
// Alien Dictionary: words sorted in an unknown alphabet; find one valid letter order ("" if impossible).
// Two neighbouring words: the first letter where they differ gives an arrow a -> b.
static String alienOrder(String[] words) {
Map<Character, Set<Character>> next = new TreeMap<>();
Map<Character, Integer> indeg = new TreeMap<>();
for (String w : words) for (char ch : w.toCharArray()) { next.putIfAbsent(ch, new TreeSet<>()); indeg.putIfAbsent(ch, 0); }
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
if (a.length() > b.length() && a.startsWith(b)) return ""; // "abc" before "ab": impossible
for (int k = 0; k < Math.min(a.length(), b.length()); k++)
if (a.charAt(k) != b.charAt(k)) {
if (next.get(a.charAt(k)).add(b.charAt(k))) indeg.merge(b.charAt(k), 1, Integer::sum);
break;
}
}
Deque<Character> q = new ArrayDeque<>();
for (var e : indeg.entrySet()) if (e.getValue() == 0) q.add(e.getKey());
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
char c = q.poll(); sb.append(c);
for (char d : next.get(c)) if (indeg.merge(d, -1, Integer::sum) == 0) q.add(d);
}
return sb.length() == indeg.size() ? sb.toString() : "";
}
public static void main(String[] args) {
System.out.println(alienOrder(new String[]{"wrt", "wrf", "er", "ett", "rftt"}));
System.out.println("[" + alienOrder(new String[]{"z", "x", "z"}) + "]");
}
}
wertf
[]
3. The smallest-numbered valid order. Among all valid orders, return the one that is smallest when read left to right.
Solution
Use a min-heap (PriorityQueue, episode 43) instead of the queue, so the smallest ready course is always taken first. Time O((V + E) log V).
import java.util.*;
public class Main {
// The smallest-numbered valid order: replace the queue with a min-heap, so the smallest ready course is taken first.
static int[] smallestOrder(int n, int[][] pre) {
List<List<Integer>> next = new ArrayList<>();
for (int c = 0; c < n; c++) next.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : pre) { next.get(p[1]).add(p[0]); indeg[p[0]]++; }
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int c = 0; c < n; c++) if (indeg[c] == 0) pq.add(c);
int[] order = new int[n]; int k = 0;
while (!pq.isEmpty()) {
int c = pq.poll(); order[k++] = c;
for (int d : next.get(c)) if (--indeg[d] == 0) pq.add(d);
}
return k == n ? order : new int[0];
}
public static void main(String[] args) {
// 3 needs 4, 1 needs 4, 2 needs 0
System.out.println(Arrays.toString(smallestOrder(5, new int[][]{{3, 4}, {1, 4}, {2, 0}})));
}
}
[0, 2, 4, 1, 3]
4. Is a given order valid? Given n, the prerequisites and a proposed order, check it.
Solution
Store pos[course] = index in the order (and check every course appears exactly once). Then for every pair [a, b], the order is valid only if pos[b] < pos[a]. O(V + E).
Quick quiz
n = 4, pairs [1,0] [2,1] [3,0] (take b before a). Which order is not valid?
A) 0, 3, 1, 2 B) 0, 1, 3, 2 C) 0, 1, 2, 3 D) 3, 0, 1, 2
Answer
D. Course 3 needs course 0, so 3 can't come before 0. The other three keep 0 before 1 and 3, and 1 before 2: there can be many topological orders.
Interview questions
- What is a topological order, and when does one exist? An order of all vertices where every arrow points forward. It exists exactly when the directed graph has no cycle (a DAG).
- How does Kahn's algorithm detect a cycle? Vertices on a cycle never reach in-degree 0, so fewer than
nvertices are output. - Why a queue? Would a stack work? Any container works: every vertex taken has in-degree 0, so any order of taking them is valid. A queue gives levels (useful for "minimum semesters"); a min-heap gives the smallest order.
- Kahn vs DFS? Both O(V + E). Kahn: iterative, simple cycle check, natural levels. DFS: reverse of finishing order; needs an iterative version for deep graphs.
- What does
[a, b]mean in LeetCode 207? Takebbeforea: the arrow isb → a. Getting this backwards is the most common bug. - Real uses? Build systems (compile a file after the files it imports), package managers, spreadsheet recalculation, task scheduling, course planning.
Glossary
| Term | Meaning |
|---|---|
| Prerequisite | A course that must come first |
| Dependency | "A depends on B": A needs B first |
Arrow b → a |
Take b before a |
| DAG | Directed acyclic graph: directed, no cycle |
| Topological order | Every arrow points from earlier to later |
| In-degree / out-degree | Arrows coming in / going out |
| Kahn's algorithm | Take in-degree-0 vertices, remove their arrows, repeat |
| Level | Vertices that become ready together |
| Cycle | A path back to its start; makes an order impossible |
| Min-heap | Always gives the smallest element first (PriorityQueue) |
| O(V + E) | Time that grows with vertices plus edges |
Summary
- Prerequisites are arrows from the first course to the later one; in LeetCode's
[a, b],bcomes first. - A topological order makes every arrow point forward; there can be many.
- Kahn's algorithm: count in-degrees, queue the zeros, poll, cross out arrows, queue new zeros.
- Fewer than
ntaken = a cycle = impossible. - O(V + E) time and space.
- Next episode: Dijkstra's algorithm, shortest paths when every edge has a weight.