269. Alien Dictionary

At a Glance

Topic: graphs
Pattern: Topological sort on a character graph inferred from adjacent words
Difficulty: Hard
Companies: Google, Amazon, Meta, Dropbox, Airbnb
Frequency: High
LeetCode: 269 (Premium)

Problem (one-liner)

Given a sorted (alien order) list of unique words, derive any valid order of letters for the alphabet. If no valid order exists (cycle or insufficient info), return "".

Recognition Cues

Lexicographic order of words implies constraints between first differing letters
Unknown letters appearing only in longer words still need placement — collect all characters first
Invalid input: prefix appears after longerword... (impossible in sorted list)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute — try all permutations of alphabet subset — factorial.
Build graph + Kahn / DFS color — O(totalChars + edges) where edges <= sum len(words) — optimal.

Optimal Solution

Go

func alienOrder(words []string) string {
	if len(words) == 0 {
		return ""
	}
	adjacency := make(map[byte][]byte)
	indegree := make(map[byte]int)
	for _, word := range words {
		for index := 0; index < len(word); index++ {
			letter := word[index]
			if _, exists := indegree[letter]; !exists {
				indegree[letter] = 0
			}
		}
	}
	for wordIndex := 0; wordIndex < len(words)-1; wordIndex++ {
		current := words[wordIndex]
		nextWord := words[wordIndex+1]
		if len(current) > len(nextWord) && hasPrefix(current, nextWord) {
			return ""
		}
		limit := len(current)
		if len(nextWord) < limit {
			limit = len(nextWord)
		}
		for charIndex := 0; charIndex < limit; charIndex++ {
			if current[charIndex] != nextWord[charIndex] {
				from := current[charIndex]
				to := nextWord[charIndex]
				adjacency[from] = append(adjacency[from], to)
				indegree[to]++
				break
			}
		}
	}
	queue := make([]byte, 0)
	for letter := range indegree {
		if indegree[letter] == 0 {
			queue = append(queue, letter)
		}
	}
	result := make([]byte, 0, len(indegree))
	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]
		result = append(result, current)
		for _, neighbor := range adjacency[current] {
			indegree[neighbor]--
			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	if len(result) != len(indegree) {
		return ""
	}
	return string(result)
}

func hasPrefix(word string, prefix string) bool {
	if len(prefix) > len(word) {
		return false
	}
	for index := 0; index < len(prefix); index++ {
		if word[index] != prefix[index] {
			return false
		}
	}
	return true
}

JavaScript

function alienOrder(words) {
  if (words.length === 0) {
    return '';
  }
  const adjacency = new Map();
  const indegree = new Map();
  const addLetter = (letter) => {
    if (!indegree.has(letter)) {
      indegree.set(letter, 0);
      adjacency.set(letter, []);
    }
  };
  for (const word of words) {
    for (const letter of word) {
      addLetter(letter);
    }
  }
  for (let wordIndex = 0; wordIndex < words.length - 1; wordIndex += 1) {
    const current = words[wordIndex];
    const nextWord = words[wordIndex + 1];
    if (current.length > nextWord.length && current.startsWith(nextWord)) {
      return '';
    }
    const limit = Math.min(current.length, nextWord.length);
    for (let charIndex = 0; charIndex < limit; charIndex += 1) {
      if (current[charIndex] !== nextWord[charIndex]) {
        const from = current[charIndex];
        const to = nextWord[charIndex];
        adjacency.get(from).push(to);
        indegree.set(to, indegree.get(to) + 1);
        break;
      }
    }
  }
  const queue = [];
  for (const [letter, degree] of indegree) {
    if (degree === 0) {
      queue.push(letter);
    }
  }
  const result = [];
  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);
    for (const neighbor of adjacency.get(current)) {
      indegree.set(neighbor, indegree.get(neighbor) - 1);
      if (indegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    }
  }
  if (result.length !== indegree.size) {
    return '';
  }
  return result.join('');
}

Walkthrough

Words ["wrt","wrf","er","ett","rftt"]: first pair wrt vs wrf gives t -> f; wrf vs er gives w -> e; etc. Build indegree, Kahn output wertf variant consistent with edges.

Invariant: Letters processed when indegree 0 are not downstream of any remaining constraint.

Edge Cases

Prefix violation — ["abc","ab"] invalid — return ""
One word — any topological order of its unique letters (often return letters in appearance order)
Disconnected graph components — Kahn may alternate; still valid if acyclic

Pitfalls

Duplicate edges between same letters — double-count indegree (dedupe neighbors or track edges added)
Ignoring letters that never appear in comparisons — still must appear in output

Variants

Return all valid topological orders — backtracking with pruning.
Known alphabet size with unknown letters — add synthetic constraints or union ranking rules.
Streaming word list — maintain cycle detection incrementally.

Mind-Map Tags

#topological-sort #character-graph #indegree #kahn-bfs #invalid-prefix-check