Alien Dictionary: Topological Sort from Word Ordering

The alien dictionary problem is a beautiful application of topological sorting. Given a list of words sorted in an alien language’s alphabetical order, determine the order of characters in that language. The trick is recognizing that adjacent word pairs give you ordering constraints, which form a directed acyclic graph (DAG). Topological sort on this DAG produces the character ordering.

The Core Insight

When words are sorted, comparing adjacent words reveals which character comes first. Consider “wrt” before “wrf”. The first two characters match (“wr”), but the third differs: ‘t’ vs ‘f’. Since “wrt” comes before “wrf” in the alien order, we know that ‘t’ comes before ‘f’ in the alien alphabet.

This gives us a directed edge: t -> f (t must come before f).

By comparing every adjacent pair of words, we extract all ordering constraints. Then topological sort gives us a valid character ordering.

Step-by-Step Algorithm

1. Compare adjacent words to extract edges
2. Build a directed graph from these edges
3. Run topological sort (Kahn’s BFS or DFS)
4. Handle edge cases: cycles (invalid), prefix issues

Full Implementation: Kahn’s BFS

from collections import defaultdict, deque

def alienOrder(words: list[str]) -> str:
    """
    LeetCode 269: Alien Dictionary.
    Returns character ordering, or "" if invalid.
    """
    # Step 1: Initialize graph with all unique characters
    graph = defaultdict(set)  # char -> set of chars that come after
    in_degree = {}
    
    for word in words:
        for char in word:
            if char not in in_degree:
                in_degree[char] = 0
    
    # Step 2: Compare adjacent words to extract edges
    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i + 1]
        
        # Edge case: if word1 is longer and word2 is its prefix
        # e.g., "abc" before "ab" is INVALID
        min_len = min(len(word1), len(word2))
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""
        
        # Find first differing character
        for j in range(min_len):
            if word1[j] != word2[j]:
                # word1[j] comes before word2[j]
                if word2[j] not in graph[word1[j]]:
                    graph[word1[j]].add(word2[j])
                    in_degree[word2[j]] += 1
                break  # only the first difference matters
    
    # Step 3: Kahn's topological sort (BFS)
    queue = deque()
    for char in in_degree:
        if in_degree[char] == 0:
            queue.append(char)
    
    result = []
    while queue:
        char = queue.popleft()
        result.append(char)
        
        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If not all characters are in result, there's a cycle
    if len(result) != len(in_degree):
        return ""
    
    return ''.join(result)

Walkthrough with Example

Words: [“wrt”, “wrf”, “er”, “ett”, “rftt”]

Step 1: Extract edges from adjacent pairs

Pair	First Diff	Edge
wrt, wrf	index 2: t vs f	t -> f
wrf, er	index 0: w vs e	w -> e
er, ett	index 1: r vs t	r -> t
ett, rftt	index 0: e vs r	e -> r

Step 2: Build graph

• t -> {f}
• w -> {e}
• r -> {t}
• e -> {r}
• f -> {}

In-degrees: w:0, e:1, r:1, t:1, f:1

Step 3: Kahn’s BFS

1. Queue: [w] (in-degree 0)
2. Process w, add e (in-degree 1->0). Queue: [e]. Result: [w]
3. Process e, add r (in-degree 1->0). Queue: [r]. Result: [w,e]
4. Process r, add t (in-degree 1->0). Queue: [t]. Result: [w,e,r]
5. Process t, add f (in-degree 1->0). Queue: [f]. Result: [w,e,r,t]
6. Process f. Queue empty. Result: [w,e,r,t,f]

Answer: “wertf”

DFS-Based Topological Sort

An alternative approach using DFS with 3-color cycle detection.

def alienOrder_dfs(words: list[str]) -> str:
    """DFS-based topological sort for alien dictionary."""
    graph = defaultdict(set)
    all_chars = set()
    
    for word in words:
        all_chars.update(word)
    
    # Extract edges
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        
        for j in range(min_len):
            if w1[j] != w2[j]:
                graph[w1[j]].add(w2[j])
                break
    
    # DFS with 3 states: 0=unvisited, 1=in_progress, 2=done
    state = {c: 0 for c in all_chars}
    result = []
    
    def dfs(char: str) -> bool:
        """Returns False if cycle detected."""
        if state[char] == 1:  # cycle!
            return False
        if state[char] == 2:  # already processed
            return True
        
        state[char] = 1  # mark in-progress
        
        for neighbor in graph[char]:
            if not dfs(neighbor):
                return False
        
        state[char] = 2  # mark done
        result.append(char)  # post-order
        return True
    
    for char in all_chars:
        if state[char] == 0:
            if not dfs(char):
                return ""
    
    # Post-order gives reverse topological order
    result.reverse()
    return ''.join(result)

Edge Cases to Watch

1. Prefix Problem

If “abc” comes before “ab”, this is invalid. A shorter word that is a prefix of a longer word must come first, not after.

# This check is critical
if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
    return ""  # INVALID ordering

2. Duplicate Words

Adjacent identical words give no information. Do not add any edges.

3. Multiple Valid Orderings

If the graph has multiple valid topological orders, any one is acceptable. Kahn’s BFS gives a deterministic order based on the queue (you could use a min-heap for lexicographic smallest).

4. Characters Not in Any Edge

Characters that appear in words but never differ in adjacent comparisons have no ordering constraints. They can go anywhere in the result. Both Kahn’s and DFS handle this correctly.

Course Schedule (LeetCode 207)

The classic topological sort problem. Can you finish all courses given prerequisites?

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    """
    LeetCode 207: Course Schedule.
    Can we take all courses? (Is the graph a DAG?)
    """
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Kahn's BFS
    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)
    
    taken = 0
    while queue:
        course = queue.popleft()
        taken += 1
        
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)
    
    return taken == numCourses

Course Schedule II (LeetCode 210)

Return the ordering of courses (topological order).

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    """
    LeetCode 210: Return a valid course ordering.
    """
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)
    
    order = []
    while queue:
        course = queue.popleft()
        order.append(course)
        
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)
    
    return order if len(order) == numCourses else []

Prerequisite Chains: Longest Path in DAG

Find the longest chain of prerequisites. This is the longest path in a DAG, solvable with topological sort + DP.

def longest_prerequisite_chain(numCourses: int, 
                                prerequisites: list[list[int]]) -> int:
    """
    Find the longest chain of prerequisites.
    This is the longest path in the prerequisite DAG.
    """
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Topological sort with DP for longest path
    queue = deque()
    longest = [1] * numCourses  # minimum chain length is 1 (the course itself)
    
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)
    
    while queue:
        course = queue.popleft()
        for next_course in graph[course]:
            longest[next_course] = max(longest[next_course], 
                                        longest[course] + 1)
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)
    
    return max(longest)

Parallel Courses (LeetCode 1136)

Find the minimum number of semesters to complete all courses, where courses with no prerequisite conflicts can be taken in parallel.

def minimumSemesters(n: int, relations: list[list[int]]) -> int:
    """
    LeetCode 1136: Minimum semesters = longest path in DAG + 1.
    This equals the number of levels in topological sort.
    """
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)
    
    for prereq, course in relations:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque()
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            queue.append(i)
    
    semesters = 0
    taken = 0
    
    while queue:
        semesters += 1
        next_queue = deque()
        
        for _ in range(len(queue)):
            course = queue.popleft()
            taken += 1
            
            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    next_queue.append(next_course)
        
        queue = next_queue
    
    return semesters if taken == n else -1

Verifying Alien Dictionary (LeetCode 953)

The inverse problem: given the character order, verify that the words are sorted correctly.

def isAlienSorted(words: list[str], order: str) -> bool:
    """
    LeetCode 953: Are words sorted in the given alien order?
    """
    # Map each character to its priority
    priority = {c: i for i, c in enumerate(order)}
    
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        
        # Compare character by character
        for j in range(min(len(w1), len(w2))):
            if w1[j] != w2[j]:
                if priority[w1[j]] > priority[w2[j]]:
                    return False
                break
        else:
            # All compared chars equal; shorter word should come first
            if len(w1) > len(w2):
                return False
    
    return True

Complexity Analysis

Problem	Time	Space
Alien Dictionary	O(C) where C = total chars in all words	O(U) where U = unique chars
Course Schedule	O(V + E)	O(V + E)
Longest Prereq Chain	O(V + E)	O(V + E)
Parallel Courses	O(V + E)	O(V + E)
Verify Alien Sorted	O(C) total chars	O(1) for the mapping

For the alien dictionary, we compare each adjacent pair and scan characters once. Building the graph is O(C). Topological sort is O(V + E) where V = unique characters (at most 26) and E = number of edges (at most 26^2). So the total is dominated by O(C).

Kahn’s BFS vs DFS Topological Sort

Aspect	Kahn’s BFS	DFS Post-Order
Cycle detection	len(result) != num_nodes	3-color state (in-progress = cycle)
Order	Natural (front to back)	Reverse post-order
Level info	Easy to get (queue levels)	Harder to extract
Implementation	In-degree array + queue	Recursion + state array
Preference	When you need levels or lexicographic order	When you need any valid order quickly

Practice Problems

Problem	Difficulty	Key Concept
LeetCode 269: Alien Dictionary	Hard	Core alien dictionary
LeetCode 953: Verifying Alien Dictionary	Easy	Verification variant
LeetCode 207: Course Schedule	Medium	DAG cycle detection
LeetCode 210: Course Schedule II	Medium	Topological ordering
LeetCode 1136: Parallel Courses	Medium	Level-based topo sort
LeetCode 2115: Find All Possible Recipes	Medium	Topo sort with supplies
LeetCode 802: Find Eventual Safe States	Medium	Reverse topo sort

Key Takeaways

1. Adjacent word comparison gives ONE edge. Only the first differing character matters; subsequent characters give no information.
2. Prefix validation is critical. “abc” before “ab” is always invalid regardless of the alphabet.
3. Cycle = invalid ordering. If topological sort cannot process all nodes, the input is contradictory.
4. Topological sort is the go-to for dependency problems. Courses, build systems, task scheduling all reduce to this.
5. Kahn’s BFS gives level information for free, useful for parallel scheduling problems.