{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Alien Dictionary – Solution & Complexity

Interview solutions
/
Alien Dictionary

Solution Walkthrough

1. Infer the graph carefully

  • The sorted dictionary does not compare every pair of letters directly.
  • From two adjacent words, only the first differing position matters; later characters tell you nothing new about order.

2. Brute-force baseline

  • You could guess permutations of the distinct letters and test whether they respect the sorted list.
  • That is factorial in the number of letters, so it becomes unusable quickly.

3. Topological sort with deterministic tie-breaking

  • Build a directed graph and indegree count from adjacent-word comparisons.
  • Reject the invalid prefix case immediately: if word1 starts with word2 and word1 is longer, there is no valid alphabet.
  • Then run Kahn's algorithm, but always remove the smallest zero-indegree character first so the final order is lexicographically smallest.

4. Final solution (all languages)

The graph has one node per distinct character. The min-priority frontier makes the topological order deterministic.

from heapq import heappop, heappush

def alien_order(words: list[str]) -> str:
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for i in range(len(words) - 1):
        first = words[i]
        second = words[i + 1]
        if len(first) > len(second) and first.startswith(second):
            return ""

        for a, b in zip(first, second):
            if a == b:
                continue
            if b not in graph[a]:
                graph[a].add(b)
                indegree[b] += 1
            break

    heap: list[str] = []
    for char, degree in indegree.items():
        if degree == 0:
            heappush(heap, char)

    order: list[str] = []
    while heap:
        char = heappop(heap)
        order.append(char)
        for neighbor in graph[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                heappush(heap, neighbor)

    return ''.join(order) if len(order) == len(indegree) else ''

5. Common mistakes and follow-ups

  • Comparing all differing positions between two words instead of only the first one.
  • Forgetting the invalid-prefix case, which produces a graph that looks acyclic but still contradicts the sorted dictionary.
  • Follow-up: if any valid order were acceptable, you could replace the min-priority frontier with a plain queue or stack of zero-indegree letters.

FAQ

See also

Practice Alien Dictionary online (run code in the browser)Course Schedule solution (medium)Word Ladder solution (hard)Clone Graph solution (medium)Connected Components in an Undirected Graph solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?