30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 269. Alien Dictionary

Given a sorted list of words in an unknown alphabet, infer the relative ordering of characters by deriving precedence constraints between first differing letters, then produce a valid topological ordering of the resulting directed graph or detect that no valid order exists (cycle or invalid prefix).

Asked at:

DESCRIPTION

Input:


words = ['wrt', 'wrf', 'er', 't', 'ett']

Output:


'wertf'

Explanation: From adjacent pairs: 'wrt' vs 'wrf' gives t→f, 'wrf' vs 'er' gives w→e, 'er' vs 't' gives e→t, 't' vs 'ett' gives t→e (already have e→t, consistent). Order: w→e→r→t→f

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters
The words are sorted lexicographically according to the alien alphabet
If no valid ordering exists, return empty string

Understanding the Problem

Let's understand what we're being asked to do. We have a sorted list of words from an unknown alphabet (not English!), like ['wrt', 'wrf', 'er', 't', 'ett'], and we need to figure out the order of characters in this alien alphabet.

The key insight: words are sorted according to this alien alphabet's rules. So if 'wrt' comes before 'wrf', we know that in this alphabet, 't' comes before 'f' (since that's the first differing character).

Let's trace through: comparing 'wrt' and 'wrf' → first difference is at index 2: 't' vs 'f' → so t < f. Comparing 'wrf' and 'er' → first difference is at index 0: 'w' vs 'e' → so w < e. Comparing 'er' and 't' → first difference is at index 0: 'e' vs 't' → so e < t.

Important constraints: The input is a sorted list according to the alien alphabet. We need to derive the character ordering from these sorted words.

Edge cases to consider: What if there's a cycle in the ordering (impossible to satisfy)? What if one word is a prefix of another but comes after it (like ['abc', 'ab'] - invalid!)? What if some characters never appear in comparisons (they can be in any order)?

Building Intuition

Each pair of adjacent words gives us one ordering constraint. If word1 is 'wrt' and word2 is 'wrf', the first differing character tells us 't' must come before 'f' in the alphabet.

This creates a directed relationship: t → f (t comes before f). Collecting all such relationships from adjacent word pairs builds a network of ordering constraints.

These ordering constraints form a directed graph where each edge A → B means 'A comes before B in the alphabet'.

If we can find a linear ordering of characters that respects all these directed edges (no character comes before one of its predecessors), we've found the alien alphabet order! This is exactly what topological sorting solves.

Think of course prerequisites: if 'Calculus requires Algebra' and 'Algebra requires Arithmetic', you need to take them in order: Arithmetic → Algebra → Calculus.

Similarly, if we know w → e, e → t, and t → f, we can deduce the ordering: w, e, t, f. But what if we also had f → w? That creates a cycle (impossible to satisfy) - just like circular course prerequisites make graduation impossible!

Common Mistakes

Comparing all pairs of words instead of only adjacent pairs - only consecutive words in the sorted list give us direct ordering constraints

Not handling the invalid prefix case: if word1 is a prefix of word2 but comes after it in the list, the input is invalid (e.g., ['abc', 'ab'])

Forgetting to check for cycles: if topological sort doesn't process all characters, a cycle exists and no valid ordering is possible

Comparing entire words character-by-character: only the first differing character gives us ordering information, subsequent characters are irrelevant for that comparison

Not initializing in-degrees for all characters: characters that appear in words but have no incoming edges (in-degree 0) must be included in the initial queue

Optimal Solution

Build a directed graph where each edge represents a character ordering constraint derived from adjacent word pairs. For each pair of adjacent words, find the first differing character and add an edge from the character in the first word to the character in the second word. Then perform topological sort using BFS (Kahn's algorithm) with in-degree tracking: repeatedly remove nodes with in-degree 0 and add them to the result. If we can't process all characters (cycle detected) or encounter invalid prefix ordering, return empty string.

from collections import defaultdict, deque

def alien_order(words):
    """
    Infer character ordering from sorted alien dictionary words.
    Returns topological ordering or empty string if invalid.
    """
    # Build adjacency graph and in-degree map
    graph = defaultdict(set)
    in_degree = {char: 0 for word in words for char in word}
    
    # Extract ordering constraints from adjacent word pairs
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))
        
        # Check for invalid prefix (word1 is prefix of word2 but longer)
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""
        
        # Find first differing character
        for j in range(min_len):
            char1, char2 = word1[j], word2[j]
            if char1 != char2:
                # Add edge if not already present
                if char2 not in graph[char1]:
                    graph[char1].add(char2)
                    in_degree[char2] += 1
                break
    
    # Topological sort using BFS (Kahn's algorithm)
    queue = deque([char for char in in_degree if in_degree[char] == 0])
    result = []
    
    while queue:
        char = queue.popleft()
        result.append(char)
        
        # Reduce in-degree for neighbors
        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if all characters were processed (no cycle)
    if len(result) != len(in_degree):
        return ""
    
    return "".join(result)

Start alien dictionary ordering

0 / 33

Test Your Knowledge

Complexity Analysis

Time Complexity: O(C) C is the total number of characters across all words. We scan through all words once to build the graph (O(C)), then perform topological sort which visits each unique character and edge once (O(V + E) where V ≤ 26 and E ≤ 26, constant). Overall O(C) dominates.

Space Complexity: O(1) The graph stores at most 26 nodes (lowercase letters) and at most 26*25 edges, which is O(1) constant space. The queue and in-degree map also store at most 26 entries each, so O(1) space overall.

What We've Learned

Topological sort for ordering constraints: When you need to determine a valid ordering from pairwise precedence relationships (A before B, C before D), build a directed graph and use topological sort (BFS with in-degree or DFS) - this problem transforms dictionary ordering into graph edges by comparing adjacent words.
Character-by-character comparison for edge extraction: Only compare adjacent words in the sorted list, and stop at the first differing character to create a directed edge - continuing past the first difference or comparing non-adjacent words creates invalid constraints that don't follow from the given ordering.
Cycle detection equals impossible ordering: If topological sort completes but hasn't visited all nodes, or if DFS finds a back edge, the constraints contain a cycle (like A→B→C→A) meaning no valid alphabet exists - return empty string to signal impossibility rather than a partial result.
Invalid prefix validation: Before building the graph, check if a longer word appears before its prefix (like 'abc' before 'ab') - this violates sorted order and should return empty string immediately, as no alphabet can make a word come before its own prefix in dictionary order.
In-degree tracking for BFS topological sort: Maintain an in-degree map counting incoming edges for each character, then process nodes with zero in-degree first - this ensures you only add a character to the result after all its predecessors are placed, naturally handling the dependency chain.
Graph construction from implicit constraints: This pattern applies to any problem where ordering rules are implicit in data arrangement rather than explicit - course prerequisites from enrollment patterns, task scheduling from completion sequences, or dependency resolution from import statements all use the same graph-building approach.

Test Your Understanding

Why is graph the right data structure for this problem?

graph provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Google

Staff

Mid September, 2025

Uber

Senior

Late August, 2025

Uber

Senior

simplified variation

Get Premium to View All 8 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More