# LeetCode 269: Alien Dictionary — Step-by-Step Visual Trace

**Hard** — Graph | Topological Sort | BFS | String

## The Problem

Given a list of words from an alien language sorted lexicographically, determine the order of letters in the alien alphabet. Return the alien dictionary as a string, or empty string if no valid order exists.

## Approach

Build a directed graph where edges represent character ordering relationships derived from adjacent word comparisons. Use topological sorting with Kahn's algorithm to find a valid ordering of characters, detecting cycles that indicate invalid dictionaries.

**Time:** O(C) · **Space:** O(1)

## Code

```python
from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(list)
        in_degree = defaultdict(int)

        for i in range(len(words) - 1):
            word1, word2 = words[i], words[i + 1]
            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    graph[word1[j]].append(word2[j])
                    in_degree[word2[j]] += 1
                    break

        queue = deque(char for char, indeg in in_degree.items() if indeg == 0)
        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 len(result) < len(in_degree):
            return ""
        return "".join(result)
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0269_alien-dictionary)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0269_alien-dictionary) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*