198. Alien Dictionary Order

Why this mechanism works

Adjacent sorted words reveal only their first differing character: that pair imposes one necessary ordering edge. Later positions cannot add constraints once the comparison is decided. Collect all characters, deduplicate edges, detect the prefix contradiction, then topologically sort with a min-heap to resolve unconstrained choices deterministically.

State and boundaries

adj stores distinct necessary character-order edges. indegree counts unmet distinct constraints; the heap contains currently eligible characters.

Protocol

1. Register every character.
2. Compare adjacent words until their first mismatch.
3. Add that edge once, or reject a reversed prefix.
4. Heapify zero-indegree characters.
5. Emit the smallest available character and release neighbors.
6. Reject if not all characters were emitted.

Visualization

'wrt' before 'wrf' -> t < f
'wrf' before 'er'  -> w < e
'abc' before 'ab'  -> impossible prefix order

Python implementation

import heapq

def alien_order(words):
    adj = {char: set() for word in words for char in word}
    indegree = dict.fromkeys(adj, 0)
    for first, second in zip(words, words[1:]):
        for a, b in zip(first, second):
            if a != b:
                if b not in adj[a]:
                    adj[a].add(b)
                    indegree[b] += 1
                break
        else:
            if len(first) > len(second):
                return ''
    heap = [char for char in adj if indegree[char] == 0]
    heapq.heapify(heap)
    output = []
    while heap:
        char = heapq.heappop(heap)
        output.append(char)
        for neighbor in adj[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                heapq.heappush(heap, neighbor)
    return ''.join(output) if len(output) == len(adj) else ''

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='wrt'; char='w'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='wrt'; char='r'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='wrt'; char='t'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='wrf'; char='w'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='wrf'; char='r'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='wrf'; char='f'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='er'; char='e'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; word='er'; char='r'

... 51 intermediate state changes omitted ...

L23 alien_order: indegree[neighbor] -= 1
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; adj={'w':{'e'}, 'r':{'t'}, 't':{'f'}, 'f':set(), 'e':{'r'}}; indegree={'w':0, 'r':0, 't':0, 'f':0, 'e':0}; first='ett'; second='rftt'; a='e'; b='r'; heap=[]; output=['w', 'e', 'r', 't']; char='t'; neighbor='f'

L25 alien_order: heapq.heappush(heap, neighbor)
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; adj={'w':{'e'}, 'r':{'t'}, 't':{'f'}, 'f':set(), 'e':{'r'}}; indegree={'w':0, 'r':0, 't':0, 'f':0, 'e':0}; first='ett'; second='rftt'; a='e'; b='r'; heap=['f']; output=['w', 'e', 'r', 't']; char='t'; neighbor='f'

L20 alien_order: char = heapq.heappop(heap)
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; adj={'w':{'e'}, 'r':{'t'}, 't':{'f'}, 'f':set(), 'e':{'r'}}; indegree={'w':0, 'r':0, 't':0, 'f':0, 'e':0}; first='ett'; second='rftt'; a='e'; b='r'; heap=[]; output=['w', 'e', 'r', 't']; char='f'; neighbor='f'

L21 alien_order: output.append(char)
words=['wrt', 'wrf', 'er', 'ett', 'rftt']; adj={'w':{'e'}, 'r':{'t'}, 't':{'f'}, 'f':set(), 'e':{'r'}}; indegree={'w':0, 'r':0, 't':0, 'f':0, 'e':0}; first='ett'; second='rftt'; a='e'; b='r'; heap=[]; output=['w', 'e', 'r', 't', 'f']; char='f'; neighbor='f'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['abc', 'ab']; word='abc'; char='a'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['abc', 'ab']; word='abc'; char='b'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['abc', 'ab']; word='abc'; char='c'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['abc', 'ab']; word='ab'; char='a'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['abc', 'ab']; word='ab'; char='b'

L4 alien_order: adj = {char: set() for word in words for char in word}
words=['abc', 'ab']; adj={'a':set(), 'b':set(), 'c':set()}

L5 alien_order: indegree = dict.fromkeys(adj, 0)
words=['abc', 'ab']; adj={'a':set(), 'b':set(), 'c':set()}; indegree={'a':0, 'b':0, 'c':0}

L6 alien_order: for first, second in zip(words, words[1:]):
words=['abc', 'ab']; adj={'a':set(), 'b':set(), 'c':set()}; indegree={'a':0, 'b':0, 'c':0}; first='abc'; second='ab'

L7 alien_order: for a, b in zip(first, second):
words=['abc', 'ab']; adj={'a':set(), 'b':set(), 'c':set()}; indegree={'a':0, 'b':0, 'c':0}; first='abc'; second='ab'; a='a'; b='a'

L7 alien_order: for a, b in zip(first, second):
words=['abc', 'ab']; adj={'a':set(), 'b':set(), 'c':set()}; indegree={'a':0, 'b':0, 'c':0}; first='abc'; second='ab'; a='b'; b='b'

Why the solution is correct

The first mismatch or prefix relation fully determines each adjacent lexical comparison. Therefore satisfying all extracted edges satisfies the given list. Kahn processing respects those edges; choosing the smallest currently feasible character is the smallest possible next character of any valid order. A cycle or reversed prefix makes an order impossible.

Time and space

O(S+E+A log A) time for S input characters, A distinct characters and E distinct inferred edges; O(A+E) auxiliary space.

Common mistakes

Inferring edges from every mismatching position invents constraints. Counting a duplicate edge twice but removing it once breaks indegrees.

Reasoning card

Transfer exercise

Detect whether the valid alphabet order is unique by observing how many characters are eligible at each step.