Alien Dictionary: Deriving Order with Topological Sort
Solve Alien Dictionary with topological sort and Kahn's algorithm: derive the alien alphabet from a sorted word list, with JavaScript code and a walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You're handed a dictionary from an alien language. Same 26 letters as English, but nobody told you the order — maybe t comes before f, maybe w comes first. All you get is a list of words, already sorted according to the alien rules. Your job: recover the alphabet.
The trick is realizing you don't need to know the ordering to reconstruct it. Two words sitting next to each other in a sorted list leak exactly one fact each, and those facts chain together into a graph. Sort the graph and you've sorted the alphabet. This is one of the cleanest applications of topological sort you'll meet in an interview.
The problem
You're given a list of strings words from an alien language's dictionary. The words are sorted lexicographically by the (unknown) rules of that language. Return a string of the unique letters in the correct order. If no valid order exists, return "".
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf" // w < e < r < t < fTwo facts hide inside "sorted lexicographically":
- Comparing two adjacent words, the first position where they differ tells you which letter is smaller. Everything before that position is identical and reveals nothing.
- If a word is a prefix of the one before it — like
"ab"after"abc"— the list can't be validly sorted, and the answer is"".
The brute force baseline
Without a pattern, the mechanical approach is to guess. Generate every permutation of the unique letters, then check whether the whole word list is actually sorted under that guess. Return the first permutation that survives.
function alienOrderBrute(words) {
const chars = [...new Set(words.join(""))];
for (const perm of permutations(chars)) {
const rank = new Map(perm.map((c, i) => [c, i]));
if (isSorted(words, rank)) return perm.join("");
}
return "";
}isSorted walks each adjacent pair and confirms the earlier word is not greater under rank. Correct, but hopeless: there are V! permutations for V distinct letters. With just 10 unique characters that's 3.6 million guesses, and a full 26-letter alphabet is 26! — more permutations than atoms in a small planet. You need to build the ordering, not search for it.
The key insight
Each adjacent pair of words is a single ordering rule. "wrt" before "wrf" — scan left to right, and the first mismatch is t vs f at index 2. That means t comes before f. One rule, one directed edge: t → f.
Collect every such edge and you have a directed graph where an edge a → b means "a precedes b." A valid alphabet is any ordering of the nodes that respects every edge — a topological ordering. And when the rules contradict each other (a cycle), no ordering exists, which is exactly the "" case.
To produce the ordering, use Kahn's algorithm: track each node's in-degree (how many letters must come before it), start from the letters with in-degree 0, and peel them off one at a time, relaxing their outgoing edges as you go. If you can't place every letter, the graph had a cycle.
The optimal solution
This is the exact algorithm the visualizer animates — build the graph, then run Kahn's BFS.
function alienOrder(words) {
const adj = new Map();
const inDegree = new Map();
for (const word of words) {
for (const char of word) {
inDegree.set(char, 0);
adj.set(char, []);
}
}
for (let i = 0; i < words.length - 1; i++) {
const w1 = words[i], w2 = words[i + 1];
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]) {
adj.get(w1[j]).push(w2[j]);
inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
break;
}
}
}
const queue = [];
for (const [char, count] of inDegree) {
if (count === 0) queue.push(char);
}
let result = "";
while (queue.length > 0) {
const char = queue.shift();
result += char;
for (const next of adj.get(char)) {
inDegree.set(next, inDegree.get(next) - 1);
if (inDegree.get(next) === 0) queue.push(next);
}
}
return result.length === inDegree.size ? result : "";
}Three phases, each doing one job. First, register every letter as a node with in-degree 0 — even letters that end up with no constraints must appear in the answer. Second, walk adjacent word pairs and add one edge per pair (the break is load-bearing: only the first mismatch is a real rule). Third, run Kahn's algorithm and, at the end, compare result.length to the number of unique letters. A short result means some letters were trapped in a cycle, so return "".
Walkthrough
Trace words = ["wrt", "wrf", "er", "ett", "rftt"]. First the graph-building pass compares each adjacent pair and records the first mismatch:
| Pair compared | First mismatch | Edge added | Effect |
|---|---|---|---|
"wrt" vs "wrf" | index 2: t ≠ f | t → f | inDegree[f] = 1 |
"wrf" vs "er" | index 0: w ≠ e | w → e | inDegree[e] = 1 |
"er" vs "ett" | index 1: r ≠ t | r → t | inDegree[t] = 1 |
"ett" vs "rftt" | index 0: e ≠ r | e → r | inDegree[r] = 1 |
After building: adj = { w:[e], r:[t], t:[f], e:[r], f:[] } and in-degrees w:0, r:1, t:1, f:1, e:1. Only w has in-degree 0, so the queue starts as [w]. Now Kahn's algorithm drains it:
| Pop | result | Edge relaxed | New in-degree | Queue after |
|---|---|---|---|---|
w | "w" | w → e | e: 1 → 0 | [e] |
e | "we" | e → r | r: 1 → 0 | [r] |
r | "wer" | r → t | t: 1 → 0 | [t] |
t | "wert" | t → f | f: 1 → 0 | [f] |
f | "wertf" | none | — | [] |
result.length is 5 and there are 5 unique letters, so the answer is "wertf". Every letter came out exactly when its last prerequisite was placed — that's the whole point of tracking in-degree.
Complexity
Let C be the total number of characters across all words, V the count of unique letters (at most 26), and E the number of edges (at most words.length − 1).
| Metric | Big-O | Why |
|---|---|---|
| Time | O(C) | Every character is touched a constant number of times: once when registering nodes, once when scanning pairs; Kahn's O(V + E) is dwarfed by C |
| Space | O(V + E) | The adjacency list and in-degree map, bounded by 26 nodes and one edge per adjacent word pair |
Because V maxes out at 26, you can call the space O(1) in an interview, but O(V + E) is the honest bound.
Common mistakes
- Adding an edge for every differing position. Only the first mismatch between two words is a real constraint. Miss the
breakand you invent edges that were never implied, corrupting the ordering. - Forgetting the prefix check.
["abc", "ab"]is invalid — a longer word can never sort before its own prefix. Without thew1.length > w2.length && w1.startsWith(w2)guard, you'd silently return a wrong answer instead of"". - Comparing non-adjacent words. Only neighboring pairs give direct rules. Comparing word 1 to word 3 assumes transitivity you haven't proven yet.
- Dropping constraint-free letters. A letter that appears but never differs still belongs in the output. Registering every character as a node up front is what keeps it there.
- Skipping cycle detection. Contradictory rules (
z → xandx → z) leave some letters stuck with a positive in-degree forever. Theresult.length === inDegree.sizecheck is your only signal that this happened.
Where this pattern shows up next
The "turn constraints into a graph, then sort or traverse it" move powers a whole family of problems:
- Clone Graph — the same adjacency-list mental model, this time copying a graph node by node.
- Max Area of Island — grid traversal where connected components replace explicit edges.
- Find if Path Exists in Graph — reachability on a graph you build from an edge list.
- All Paths From Source to Target — enumerating orderings through a directed acyclic graph, the flip side of collapsing one out.
You can also step through Alien Dictionary interactively to watch the constraint graph fill in and Kahn's queue drain one letter at a time.
FAQ
Why is Alien Dictionary a topological sort problem?
Because the answer is an ordering that must respect a set of "before" constraints. Each adjacent pair of sorted words tells you one letter comes before another, which is exactly a directed edge. A valid alphabet is any linear ordering of the letters consistent with every edge — the textbook definition of a topological ordering. Kahn's algorithm produces one such ordering (or proves none exists) in linear time.
How do you detect that no valid ordering exists?
Two ways, both in the solution. First, a prefix violation: if a word is a prefix of the one that came before it, like "ab" after "abc", the dictionary itself is inconsistent and you return "" immediately. Second, a cycle in the constraint graph: if the rules contradict each other, some letters keep a positive in-degree and never enter the queue. After Kahn's algorithm finishes, compare the result length to the number of unique letters — if it's short, a cycle blocked those letters and the answer is "".
Why only compare adjacent words instead of every pair?
Sorted order is transitive, so adjacent pairs already capture everything. If word A sorts before B and B before C, the rule between A and C is implied by chaining the two adjacent rules through the graph — you don't need to add it directly. Comparing every pair would add redundant edges at best and, worse, tempt you into assuming an ordering between words that share no differing prefix. Adjacent pairs give the minimal, correct set of constraints.
What is the time complexity of the Alien Dictionary solution?
O(C), where C is the total number of characters across all the input words. Registering nodes touches every character once, scanning adjacent pairs touches each character at most once more, and Kahn's algorithm runs in O(V + E) — bounded by 26 letters and one edge per word pair, which C dominates. Space is O(V + E) for the adjacency list and in-degree map, effectively constant since there are at most 26 distinct letters.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.