Alien Dictionary Using Topological Sort

Problem Statement❯

The Alien Dictionary problem asks: Given a sorted dictionary of an alien language containing N words and K unique starting characters (from a known alphabet), determine the correct order of characters in the alien language.

The words are sorted lexicographically according to the rules of the alien language. By comparing adjacent words, we can derive the ordering of some characters. Our goal is to derive a valid total character order that satisfies all such pairwise orderings.

Note: Multiple valid orders may exist for the same input.

Examples❯

Words	K	Possible Order	Description
["baa", "abcd", "abca", "cab", "cad"]	4	b → d → a → c	Valid topological ordering derived from character precedence
["caa", "aaa", "aab"]	3	c → a → b	‘c’ comes before ‘a’, and ‘a’ before ‘b’
["abc", "ab"]	3	Invalid input	Second word is a prefix of the first, contradicting lexicographical order
[]	0	""	Empty dictionary, no order possible
["x"]	1	x	Only one character, trivially ordered

Solution❯

Understanding the Problem

You're given a list of words sorted in lexicographical order according to an unknown language. The task is to deduce the order of characters in that alien language.

Building the Graph

First, we treat each character as a node in a graph. By comparing adjacent words in the dictionary, we can determine the relative order of characters. For example, if the first difference between two words is that 'x' comes before 'y', then we can say 'x' → 'y'.

Handling Edge Cases

It’s important to ensure that invalid inputs are caught. For instance, if a longer word comes before its prefix (e.g., “apple” before “app”), then it's not a valid dictionary and should return an empty string or an error.

Topological Sorting with BFS (Kahn’s Algorithm)

After constructing the graph, we perform a topological sort. We track how many incoming edges each character has (in-degree). Characters with 0 in-degree can be processed first. As we "remove" them from the graph, we reduce the in-degree of connected nodes. If we’re able to include all K characters in the result, we have a valid order.

Cycle Detection

If at any point we cannot find a node with 0 in-degree but not all nodes are processed, it indicates a cycle—meaning contradictory rules exist in the input. In this case, no valid ordering can be determined.

Final Output

If everything goes well, the characters in the result form the correct order of the alien alphabet. Otherwise, if the result string length is less than K, it means some characters could not be ordered due to a cycle or disconnected components.

Algorithm Steps❯

Initialize an adjacency list and an in-degree map for all K characters.
Compare each pair of adjacent words to extract precedence rules (edges).
Build the graph and update the in-degrees of each character.
Use a queue to perform BFS (Kahn’s algorithm):
1. Push characters with in-degree 0 into the queue.
2. Pop from queue, add to result string.
3. Decrease in-degrees of neighbors, and push those with 0 in-degree.
If the result string has length K, return it as the answer. Otherwise, input had a cycle or inconsistency.

Code

JavaScript

function alienOrder(words, k) {
  const adj = Array.from({ length: k }, () => []);
  const indegree = new Array(k).fill(0);

  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const minLen = Math.min(w1.length, w2.length);
    let found = false;

    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        adj[w1.charCodeAt(j) - 97].push(w2.charCodeAt(j) - 97);
        indegree[w2.charCodeAt(j) - 97]++;
        found = true;
        break;
      }
    }

    if (!found && w1.length > w2.length) return ""; // invalid
  }

  const queue = [];
  for (let i = 0; i < k; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length > 0) {
    const u = queue.shift();
    order.push(String.fromCharCode(u + 97));

    for (const v of adj[u]) {
      indegree[v]--;
      if (indegree[v] === 0) queue.push(v);
    }
  }

  return order.length === k ? order.join('') : "";
}

console.log("Order:", alienOrder(["caa","aaa","aab"], 3));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(N + K)	We must iterate through all N characters to build the graph and process up to K nodes during topological sort. No skipping possible.
Average Case	O(N + K)	Building edges between characters takes O(N) time and topological sorting over K nodes also takes O(K).
Worst Case	O(N + K)	Even if all characters are interconnected, we must build the graph using all N words and sort up to K characters.

Space Complexity❯

O(K + E)

Explanation: We store an adjacency list for up to K characters and E edges (from character precedence rules), and also track in-degree for K nodes.

⬅ Previous TopicFind Eventual Safe States in a Directed Graph

Next Topic ⮕Shortest Path in Undirected Graph with Unit Distance