Solving Alien Dictionary in JavaScript: Step-by-Step Guide
The Alien Dictionary problem is a classic graph and topological sorting challenge that frequently appears in technical interviews at major tech companies. It tests your ability to model relationships as a graph, detect cycles, and produce a valid ordering of nodes. In this tutorial, we will break down the problem, understand the underlying concepts, and implement a complete solution in JavaScript.
What Is the Alien Dictionary Problem?
Imagine you have discovered a dictionary from an alien civilization. The dictionary contains words sorted lexicographically according to the alien language's alphabet. However, you do not know the order of characters in that alphabet. Your task is to reconstruct the character order from the given list of sorted words.
For example, given the input:
["wrt", "wrf", "er", "ett", "rftt"]The correct character order would be "wertf". The reasoning comes from comparing adjacent words and extracting ordering rules between characters.
Why It Matters
This problem matters for several reasons:
- Real-world relevance: It mirrors how compilers and interpreters resolve dependency orders, such as import resolution or build system scheduling.
- Graph modeling skills: It trains you to translate a textual problem into a graph representation with directed edges.
- Topological sorting mastery: Topological sort is a foundational algorithm used in task scheduling, course prerequisite resolution, and data pipeline orchestration.
- Cycle detection: The problem requires detecting invalid inputs where no valid ordering exists, a critical skill for robust software.
Breaking Down the Approach
The solution involves three main phases: extracting ordering rules, building a directed graph, and performing topological sort.
Step 1: Extract Ordering Rules
Compare each pair of adjacent words. Find the first position where the characters differ. That difference gives you a directed edge: the character from the first word comes before the character from the second word.
For the words "wrt" and "wrf", the first difference is at index 2, so t comes before f. For "wrf" and "er", the first difference is at index 0, so w comes before e.
There is also an edge case: if a longer word appears before a shorter word that is its prefix, the input is invalid. For example, ["abc", "ab"] is impossible because "abc" should come after "ab" in any valid lexicographical order.
Step 2: Build the Graph
Represent the graph using an adjacency list. Also track the in-degree of each node, which counts how many edges point to it. Nodes with zero in-degree have no prerequisites and can be processed first.
Step 3: Topological Sort Using Kahn's Algorithm
Kahn's algorithm uses a queue to process nodes with zero in-degree. For each node processed, decrement the in-degree of its neighbors. When a neighbor's in-degree reaches zero, add it to the queue. If the final sorted result contains fewer characters than the total unique characters, a cycle exists and the input is invalid.
Complete JavaScript Implementation
Here is the full, working implementation:
function alienOrder(words) {
// Step 1: Initialize adjacency list and in-degree map
const graph = new Map();
const inDegree = new Map();
// Ensure every unique character is represented
for (const word of words) {
for (const ch of word) {
if (!graph.has(ch)) {
graph.set(ch, new Set());
inDegree.set(ch, 0);
}
}
}
// Step 2: Build edges by comparing adjacent words
for (let i = 0; i < words.length - 1; i++) {
const word1 = words[i];
const word2 = words[i + 1];
const minLen = Math.min(word1.length, word2.length);
// Edge case: invalid prefix ordering
if (
word1.length > word2.length &&
word1.startsWith(word2)
) {
return "";
}
for (let j = 0; j < minLen; j++) {
const ch1 = word1[j];
const ch2 = word2[j];
if (ch1 !== ch2) {
const neighbors = graph.get(ch1);
if (!neighbors.has(ch2)) {
neighbors.add(ch2);
inDegree.set(ch2, inDegree.get(ch2) + 1);
}
break; // Only the first difference matters
}
}
}
// Step 3: Kahn's algorithm for topological sort
const queue = [];
for (const [ch, degree] of inDegree.entries()) {
if (degree === 0) {
queue.push(ch);
}
}
let result = "";
while (queue.length > 0) {
const ch = queue.shift();
result += ch;
for (const neighbor of graph.get(ch)) {
inDegree.set(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) === 0) {
queue.push(neighbor);
}
}
}
// If result does not include all characters, a cycle exists
if (result.length !== graph.size) {
return "";
}
return result;
}
// Example usage
const words = ["wrt", "wrf", "er", "ett", "rftt"];
console.log(alienOrder(words)); // Output: "wertf"
// Invalid input with cycle
const cyclicWords = ["z", "x", "z"];
console.log(alienOrder(cyclicWords)); // Output: ""
// Invalid prefix case
const prefixWords = ["abc", "ab"];
console.log(alienOrder(prefixWords)); // Output: ""
How to Use the Solution
Call the alienOrder function with an array of strings representing the sorted alien dictionary. The function returns a string containing the characters in their inferred order. If no valid ordering exists, it returns an empty string.
Here are a few more test cases to verify correctness:
console.log(alienOrder(["z", "x"])); // "zx"
console.log(alienOrder(["z", "x", "y"])); // "zxy"
console.log(alienOrder(["a", "b", "c", "a"])); // "" (cycle)
console.log(alienOrder(["ab", "adc"])); // "abdc" or "badc" depending on tie-breaking
console.log(alienOrder(["a", "a"])); // "a"
Complexity Analysis
Let N be the number of words and L be the maximum length of a word. Let U be the number of unique characters.
- Time complexity: O(N * L + U). Building the graph requires comparing adjacent words, which takes O(N * L). Topological sort processes each character and edge once, taking O(U) since the number of edges is bounded by U^2 but in practice is small.
- Space complexity: O(U) for the adjacency list and in-degree map, plus O(U) for the queue and result string.
Best Practices
- Always initialize all unique characters: Even characters with no edges must appear in the result. Forgetting this leads to incomplete output.
- Handle the prefix edge case early: A longer word before its shorter prefix is always invalid. Check this before building edges.
- Use a Set for adjacency lists: This prevents duplicate edges from inflating in-degree counts when the same character pair appears in multiple word comparisons.
- Detect cycles explicitly: Compare the length of the result string to the number of unique characters. A mismatch means a cycle prevented full traversal.
- Break after the first differing character: Only the first difference between adjacent words provides ordering information. Subsequent characters are irrelevant for that pair.
- Consider DFS-based topological sort as an alternative: While Kahn's algorithm is intuitive and iterative, a DFS approach with a visited and visiting set also works and may feel more natural if you are comfortable with recursion.
DFS-Based Alternative Implementation
For completeness, here is a DFS-based approach that uses a visiting state to detect cycles:
function alienOrderDFS(words) {
const graph = new Map();
for (const word of words) {
for (const ch of word) {
if (!graph.has(ch)) {
graph.set(ch, new Set());
}
}
}
for (let i = 0; i < words.length - 1; i++) {
const word1 = words[i];
const word2 = words[i + 1];
const minLen = Math.min(word1.length, word2.length);
if (word1.length > word2.length && word1.startsWith(word2)) {
return "";
}
for (let j = 0; j < minLen; j++) {
if (word1[j] !== word2[j]) {
graph.get(word1[j]).add(word2[j]);
break;
}
}
}
// State: 0 = unvisited, 1 = visiting, 2 = visited
const state = new Map();
for (const ch of graph.keys()) {
state.set(ch, 0);
}
let result = "";
function dfs(ch) {
if (state.get(ch) === 1) return false; // cycle detected
if (state.get(ch) === 2) return true; // already processed
state.set(ch, 1);
for (const neighbor of graph.get(ch)) {
if (!dfs(neighbor)) return false;
}
state.set(ch, 2);
result = ch + result; // prepend for correct order
return true;
}
for (const ch of graph.keys()) {
if (state.get(ch) === 0) {
if (!dfs(ch)) return "";
}
}
return result;
}
console.log(alienOrderDFS(["wrt", "wrf", "er", "ett", "rftt"])); // "wertf"
The DFS approach prepends each character to the result after visiting all its dependencies, which naturally produces the correct reverse-post-order needed for topological sorting.
Common Pitfalls to Avoid
- Forgetting to register isolated characters: Characters that never appear in any edge still belong in the output. Always populate the graph with every character first.
- Not breaking after the first difference: Continuing to compare characters after the first mismatch creates false edges and corrupts the ordering.
- Ignoring duplicate edges: Without a Set, adding the same edge twice increments in-degree incorrectly, which can cause the algorithm to never reach zero in-degree for some nodes.
- Mishandling the prefix case: The condition
word1.length > word2.length && word1.startsWith(word2)must be checked for every adjacent pair, not just the first.
Conclusion
The Alien Dictionary problem is a powerful exercise in graph modeling and topological sorting. By extracting ordering rules from adjacent word pairs, building a directed graph, and applying Kahn's algorithm or DFS-based topological sort, you can reconstruct the alien alphabet or determine that no valid ordering exists. Mastering this problem equips you with transferable skills for dependency resolution, task scheduling, and any domain where ordering constraints matter. Practice both the BFS and DFS variants, test against edge cases like cycles and invalid prefixes, and you will be well prepared to tackle this problem confidently in any technical interview.