This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#269) before relying on it.

Alien Dictionary

An interactive visualization of the Alien Dictionary problem. Watch how word comparisons derive ordering edges, build a character DAG, and topological sort produces the alien alphabet.

Topological Sort LeetCode 269 ↗ Hard

The Problem

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language. If the order is invalid, return "". If there are multiple valid orderings, return any of them.

Interactive Visualization

Words (comma-separated)

Preset

Speed:

1. Compare Words

2. Build DAG

3. Topological Sort

Word Comparison & DAG

Current Step

Press Step or Play to begin.

Code

fun alienOrder(words: Array<String>): String {    val graph = mutableMapOf<Char, MutableSet<Char>>()    val inDegree = mutableMapOf<Char, Int>()    words.forEach { w -> w.forEach { c -> graph.putIfAbsent(c, mutableSetOf()); inDegree.putIfAbsent(c, 0) } }    for (i in 0 until words.size - 1) {        val w1 = words[i]; val w2 = words[i + 1]        if (w1.length > w2.length && w1.startsWith(w2))            return ""  // invalid        for (j in 0 until minOf(w1.length, w2.length)) {            if (w1[j] != w2[j]) {                if (w2[j] !in graph[w1[j]]!!) {                    graph[w1[j]]!!.add(w2[j])                    inDegree[w2[j]] = inDegree[w2[j]]!! + 1                } ; break    }   }   }    val queue = ArrayDeque(inDegree.filter { it.value == 0 }.keys)    val result = StringBuilder()    while (queue.isNotEmpty()) {        val c = queue.removeFirst()        result.append(c)        for (nb in graph[c]!!) {            inDegree[nb] = inDegree[nb]!! - 1            if (inDegree[nb] == 0)                queue.addLast(nb)    }   }    return if (result.length == graph.size)        result.toString()    else ""  // cycle}

def alienOrder(words):    graph = {c: set() for w in words for c in w}    in_degree = {c: 0 for c in graph}    for i in range(len(words) - 1):        w1, w2 = words[i], words[i + 1]        if len(w1) > len(w2) and w1[:len(w2)] == w2:            return ""  # invalid        for c1, c2 in zip(w1, w2):            if c1 != c2:                if c2 not in graph[c1]:                    graph[c1].add(c2)                    in_degree[c2] += 1                break    queue = deque(c for c in in_degree if in_degree[c] == 0)    result = []    while queue:        c = queue.popleft()        result.append(c)        for neighbor in graph[c]:            in_degree[neighbor] -= 1            if in_degree[neighbor] == 0:                queue.append(neighbor)    if len(result) == len(graph):        return "".join(result)    return ""  # cycle

How It Works

Phase 1: Compare Adjacent Words

For each consecutive pair of words in the sorted list, we find the first position where the characters differ. This gives us an ordering constraint: the character in the first word comes before the character in the second word in the alien alphabet. If a longer word is a prefix of a shorter word that follows it, the input is invalid.

Phase 2: Build a Directed Acyclic Graph (DAG)

Each unique character becomes a node. Each ordering constraint becomes a directed edge. We also track the in-degree of each node (how many edges point into it). Characters with in-degree 0 have no prerequisites and can appear first.

Phase 3: Topological Sort (Kahn's BFS)

We initialize a queue with all nodes that have in-degree 0. We repeatedly dequeue a node, add it to the result, and decrement the in-degree of all its neighbors. When a neighbor's in-degree reaches 0, it enters the queue. If the result contains all characters, we have a valid ordering. Otherwise, there is a cycle.

Complexity

Time O(C)

Space O(1) or O(U + min(U^2, N))

Where C is the total length of all words combined, and U is the number of unique characters (at most 26). We scan each character at most once during word comparison, and the BFS processes each node and edge once. Since the number of unique characters is bounded by 26, the graph operations are effectively O(1) in the alphabet size.