Topological Sort: Practice Problems with Solutions
Welcome to the practice problems for topological sort. If you need a refresher on the code, the code templates have Kahn’s algorithm and the DFS alternative in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.
Recommended Study Order
The problems are ordered by difficulty, but the progression matters as much as the individual solutions.
- Course Schedule is the smallest complete Kahn’s pipeline. Build the graph, count indegrees, peel ready nodes, and check the count. Master that skeleton before adding anything else.
- Course Schedule II is the same code with the order returned instead of a boolean. If you can do problem 1, this one is nearly free.
- Sequence Reconstruction adds the uniqueness condition. A topological order is only unique when the ready queue never holds more than one node, and this problem tests exactly that.
- Minimum Height Trees flips the direction. Instead of peeling nodes with no prerequisites, you peel leaves from an undirected graph until the center remains.
- Find Eventual Safe States reverses the edges and runs the same peeling on the reversed graph. This is a different way to think about reachability.
- Alien Dictionary is the hardest because the graph is hidden inside word comparisons. You have to build the graph before you can sort it.
Easy Problems
1. Course Schedule
LeetCode 207 | Difficulty: Easy (Medium on LeetCode, but the natural entry point for this pattern)
Brief: Determine whether all courses can be finished given a list of prerequisites.
Why this pattern: A prerequisite is a directed edge, and finishing every course is exactly the question of whether a topological order exists. The order only exists when the graph is acyclic.
Key Insight: Run Kahn’s algorithm and count the processed nodes. If the count is less than the number of courses, some courses sit in a cycle where each one waits on another, so no order exists. Complexity is
Visual:
graph LR
0((0)) --> 1((1))
1((1)) --> 2((2))
2((2)) --> 0((0))
style 0 fill:#fdd,stroke:#f66
style 1 fill:#fdd,stroke:#f66
style 2 fill:#fdd,stroke:#f66
Every course in the cycle above has indegree one, so none ever becomes ready and the queue empties after processing nothing.
Code:
function canFinish(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
// Each prerequisite pair [course, prereq] is an edge
// from prereq to course
for (const [course, prereq] of prerequisites) {
adj[prereq].push(course);
indegree[course]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
let processed = 0;
while (queue.length > 0) {
const u = queue.shift();
processed++;
for (const v of adj[u]) {
indegree[v]--;
if (indegree[v] === 0) queue.push(v);
}
}
// A course inside a cycle never becomes ready,
// so processed stays below numCourses
return processed === numCourses;
}The solution is the Kahn’s template with a counter instead of the order. The processed count is the cycle detector: a course inside a cycle never reaches indegree zero, the queue empties early, and the count stays below the total. The same problem appears on the Cycle Detection practice page , where the DFS state-tracking solution is the focus. Here the ordering pipeline is the point, there the cycle itself is the point.
Medium Problems
2. Course Schedule II
LeetCode 210 | Difficulty: Medium
Brief: Return a valid course order, or an empty array if no order exists.
Why this pattern: The problem asks for the exact artifact a topological sort produces. There is nothing hidden here. Build the graph, run Kahn’s, and the result list is the answer.
Key Insight: The order in which nodes leave the queue is already a valid topological order. The only extra work is returning an empty array when the order length falls short of the course count. Complexity is
Visual:
graph TD
1((1)) --> 0((0))
2((2)) --> 0((0))
3((3)) --> 1((1))
3((3)) --> 2((2))
style 3 fill:#bfb,stroke:#090
Node 3 is the only course with no prerequisites, so it comes first, then 1 and 2 in either order, then 0. The output [3, 1, 2, 0] is valid, and so is [3, 2, 1, 0].
Code:
function findOrder(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
const order = [];
for (const [course, prereq] of prerequisites) {
adj[prereq].push(course);
indegree[course]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
while (queue.length > 0) {
const u = queue.shift();
order.push(u);
for (const v of adj[u]) {
indegree[v]--;
if (indegree[v] === 0) queue.push(v);
}
}
return order.length === numCourses ? order : [];
}The only difference from Course Schedule is what gets returned. The queue pop order is the answer, and the length check decides between a valid order and an impossible schedule. Any valid order is accepted, so there is no need to worry about which of several orders the queue produces.
3. Sequence Reconstruction
LeetCode 444 | Difficulty: Medium
Brief: Determine whether the sequence org is the unique shortest common supersequence that can be reconstructed from a list of shorter sequences.
Why this pattern: Every adjacent pair inside a sequence is a constraint that the reconstructed order must respect. Those constraints form a DAG, and the reconstruction question becomes a topological sort with an extra condition.
Key Insight: A topological order is unique exactly when the ready queue holds one node at every step. If the queue ever holds two or more nodes, either one could come next, so several orders exist. Complexity is
Visual:
graph TD
S["Ready queue: [1]"] --> P["Pop 1, matches org[0]"]
P --> Q["Ready queue: [2]"]
Q --> R["Pop 2, matches org[1]"]
R --> T["Ready queue: [3]"]
T --> U["Pop 3, matches org[2]"]
U --> F["Queue size never exceeded 1: order is unique"]
Code:
function sequenceReconstruction(org, seqs) {
const adj = new Map();
const indegree = new Map();
const nodes = new Set();
for (const seq of seqs) {
for (const x of seq) {
nodes.add(x);
if (!adj.has(x)) adj.set(x, new Set());
if (!indegree.has(x)) indegree.set(x, 0);
}
// Each adjacent pair in a sequence is a constraint
for (let i = 0; i < seq.length - 1; i++) {
if (!adj.get(seq[i]).has(seq[i + 1])) {
adj.get(seq[i]).add(seq[i + 1]);
indegree.set(seq[i + 1], indegree.get(seq[i + 1]) + 1);
}
}
}
if (nodes.size !== org.length) return false;
const queue = [];
for (const [node, count] of indegree) {
if (count === 0) queue.push(node);
}
let index = 0;
while (queue.length === 1) {
const u = queue.shift();
// A second ready node means several orders exist
if (u !== org[index++]) return false;
for (const v of adj.get(u)) {
indegree.set(v, indegree.get(v) - 1);
if (indegree.get(v) === 0) queue.push(v);
}
}
return index === org.length;
}The loop condition is the whole trick. Standard Kahn’s uses an empty check on the queue; this problem needs a size check of exactly one. When the queue holds two nodes, both could appear next, the reconstruction is not unique, and the answer is false. The size check on the node set catches sequences that cover a different set of numbers than org.
4. Minimum Height Trees
LeetCode 310 | Difficulty: Medium
Brief: Find all nodes that, when chosen as the root, produce a tree of minimum height.
Why this pattern: This is topological sort run inward instead of outward. Instead of peeling nodes with no prerequisites, you peel leaves, the nodes with only one neighbor, and stop when the center remains.
Key Insight: A tree has at most two centers, so peeling stops when two or fewer nodes remain. The remaining nodes are the roots of the minimum height trees. Complexity is
Visual:
graph TD
L0["Leaves: 0, 2, 3"] --> P1["Peel leaves, neighbors lose one edge"]
P1 --> L1["New leaves: 1"]
L1 --> R["Remaining nodes: 1"]
On the star with center 1, one round of peeling removes all three leaves and leaves the center exposed.
Code:
function findMinHeightTrees(n, edges) {
if (n === 1) return [0];
const adj = Array.from({ length: n }, () => new Set());
for (const [u, v] of edges) {
adj[u].add(v);
adj[v].add(u);
}
let leaves = [];
for (let i = 0; i < n; i++) {
if (adj[i].size === 1) leaves.push(i);
}
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const next = [];
for (const leaf of leaves) {
const neighbor = adj[leaf].values().next().value;
// Remove the leaf, the neighbor loses that edge
adj[neighbor].delete(leaf);
if (adj[neighbor].size === 1) next.push(neighbor);
}
leaves = next;
}
return leaves;
}The graph is undirected here, so indegree becomes degree and the edge direction disappears. Each round removes every current leaf and drops one edge from its neighbor, and a neighbor becomes a leaf when its degree hits one. The adjacency sets make removal constant time, which keeps the whole process linear. The two-node case returns both nodes because either root gives a tree of height one.
5. Find Eventual Safe States
LeetCode 802 | Difficulty: Medium
Brief: Return all nodes that eventually lead to a terminal node, meaning no path from them can get stuck in a cycle.
Why this pattern: Reverse every edge, and the problem becomes a topological sort. A node is safe when every path from it ends, which is exactly the set of nodes Kahn’s can reach from the reversed sources.
Key Insight: Terminal nodes have no outgoing edges, so in the reversed graph they have indegree zero. Peeling the reversed graph removes exactly the safe nodes, and every node left behind is on a path into a cycle. Complexity is
Visual:
graph TD
0((0)) --> 1((1))
1((1)) --> 2((2))
2((2)) --> 5((5))
3((3)) --> 0((0))
4((4)) --> 5((5))
style 5 fill:#bfb,stroke:#090
style 6 fill:#bfb,stroke:#090
Nodes 5 and 6 are terminal. In the reversed graph they act as sources, and the peel reaches 4 as well. Nodes 0, 1, 2, and 3 can reach the cycle 0 to 1 to 2 to 0, so they stay unsafe.
Code:
function eventualSafeNodes(graph) {
const n = graph.length;
const rev = Array.from({ length: n }, () => []);
const indegree = new Array(n).fill(0);
// Reverse the edges and count original outdegree
// as the reversed indegree
for (let u = 0; u < n; u++) {
for (const v of graph[u]) {
rev[v].push(u);
indegree[u]++;
}
}
const queue = [];
for (let i = 0; i < n; i++) {
if (indegree[i] === 0) queue.push(i);
}
const safe = new Array(n).fill(false);
while (queue.length > 0) {
const u = queue.shift();
safe[u] = true;
for (const v of rev[u]) {
indegree[v]--;
if (indegree[v] === 0) queue.push(v);
}
}
const result = [];
for (let i = 0; i < n; i++) {
if (safe[i]) result.push(i);
}
return result;
}The reversal is the key move. A path from u into a cycle becomes a path from the cycle to u in the reversed graph, so Kahn’s peeling from the reversed sources reaches exactly the nodes that never enter a cycle. The answer comes out sorted because the final scan walks the indices in order.
Hard Problems
6. Alien Dictionary
LeetCode 269 | Difficulty: Hard
Brief: Given words sorted in an alien language, derive the order of the alphabet.
Why this pattern: Two adjacent words that differ at some position reveal one ordering constraint between two characters. Collect all such constraints, build the graph, and the character order is a topological sort of it.
Key Insight: Only the first differing character between adjacent words matters. Every later character gives no information. Also, if a word is a prefix of the word that follows it, the list is invalid. Complexity is
Visual:
graph LR
w((w)) --> e((e))
e((e)) --> r((r))
r((r)) --> t((t))
t((t)) --> f((f))
Comparing “wrt” with “wrf” gives t before f. Comparing “wrf” with “er” gives w before e. Comparing “er” with “ett” gives r before t, and “ett” with “rftt” gives e before r. The chain resolves to the order w, e, r, t, f.
Code:
function alienOrder(words) {
const adj = new Map();
const indegree = new Map();
for (const word of words) {
for (const c of word) {
if (!adj.has(c)) {
adj.set(c, new Set());
indegree.set(c, 0);
}
}
}
for (let i = 0; i < words.length - 1; i++) {
const w1 = words[i], w2 = words[i + 1];
// A longer word that is a prefix of a shorter word
// contradicts the sorted order
if (w1.length > w2.length && w1.startsWith(w2)) return "";
for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
if (w1[j] !== w2[j]) {
if (!adj.get(w1[j]).has(w2[j])) {
adj.get(w1[j]).add(w2[j]);
indegree.set(w2[j], indegree.get(w2[j]) + 1);
}
break;
}
}
}
const queue = [];
for (const [c, d] of indegree) {
if (d === 0) queue.push(c);
}
const order = [];
while (queue.length > 0) {
const u = queue.shift();
order.push(u);
for (const v of adj.get(u)) {
indegree.set(v, indegree.get(v) - 1);
if (indegree.get(v) === 0) queue.push(v);
}
}
return order.length === adj.size ? order.join("") : "";
}Two traps make this problem hard. The first is the prefix case. If a word is a prefix of the following word, the sorted order is contradicted and no valid alphabet exists. The second is the final length check. A cycle among characters produces a partial order, and the answer must be an empty string, not the partial order. Any valid order is accepted when multiple orders exist, so the queue order needs no extra handling.
These six problems cover the full range of topological sort. Start with the Kahn’s skeleton in Course Schedule, add the uniqueness condition in Sequence Reconstruction, then learn the two reverse-direction variants in Minimum Height Trees and Find Eventual Safe States. Finish with Alien Dictionary, where the graph construction is as much of the problem as the sort itself. By the end, you should be able to spot a dependency graph inside almost any scheduling problem and reach for the right template.