What pattern does Alien Dictionary use?

The Pattern: Topological Sort (Cycle Detection in Directed Graph) The Heuristic: When inferring order from pairwise precedence constraints, represent characters as graph nodes and edges as 'comes before' relations; then use DFS with cycle detection to find a valid linear order or detect contradictions.

Alien Dictionary — Topological Sort

Q: What is the time complexity of Alien Dictionary?

O(C + V). Building the graph requires comparing adjacent words and their characters, which takes O(C) where C is the total number of characters across all words. The DFS topological sort visits each node and edge once, resulting in O(V + E) time, where V is the number of unique characters and E is the number of edges. Since E ≤ C, total complexity is O(C + V).

Problem

Given a list of words sorted lexicographically according to an unknown alien language, return a string representing the characters in the alien language sorted in lexicographical order. Return an empty string if no valid ordering exists.

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 100
words[i] consists of only lowercase English letters

Example

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]

Output: "wertf"

The algorithm compares adjacent words to infer ordering constraints between characters. For example, comparing "wrt" and "wrf" reveals that 't' comes before 'f'. Comparing "wrf" and "er" shows 'w' comes before 'e'. These pairwise constraints build a directed graph representing character precedence. The critical moment is detecting an invalid prefix case: if a longer word precedes a shorter word that is a prefix of it (e.g., "abc" before "ab"), the ordering is invalid, and the algorithm returns an empty string immediately.

Approach

Straightforward Solution

A naive approach might attempt to guess character orderings or try all permutations, which is infeasible due to combinatorial explosion.

Core Observation

The lexicographical order of words implies a partial order of characters. Comparing adjacent words reveals direct precedence relations between characters, which can be represented as edges in a directed graph.

Path to Optimal

Preview

The key insight is to model the problem as a graph of character precedence and perform a topological sort to find a valid linear ordering. Detecting invalid prefix cases early prevents futile computation…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build a directed graph where nodes are characters and edges represent precedence constraints derived from adjacent word comparisons. Detect invalid prefix cases by checking if a longer word precedes its prefix…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(C + V)

Building the graph requires comparing adjacent words and their characters, which takes O(C) where C is the total number of characters across all words. The DFS topological sort visits each node and edge once, resulting in O(V + E) time, where V is the number of unique characters and E is the number of edges. Since E ≤ C, total complexity is O(C + V).

Space

O(V + E)

The adjacency list stores edges for each character, requiring O(V + E) space. The recursion stack and visited dictionary use O(V) space. This auxiliary space is necessary to represent the graph and track traversal state.

Solution

Python

1class Solution:
  def alienOrder(self, words: list[str]) -> str:
      adj = { c: set() for w in words for c in w }
      
      for i in range(len(words) - 1):
          w1, w2 = words[i], words[i + 1]
          min_len = min(len(w1), len(w2))
          if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
              return ""
          for j in range(min_len):
              if w1[j] != w2[j]:
                  adj[w1[j]].add(w2[j])
                  break
      
      visit = {} 
      res = []
      
      def dfs(c):
          if c in visit:
              return visit[c]
          
          visit[c] = True
          for nei in adj[c]:
              if dfs(nei):
                  return True
          
          visit[c] = False
          res.append(c)
          
      for c in adj:
          if dfs(c):
              return ""
      
      return "".join(res[::-1])

Step-by-Step Solution

1

Construct Directed Graph of Character Precedence from Adjacent Words

3adj = { c: set() for w in words for c in w }
5for i in range(len(words) - 1):
  w1, w2 = words[i], words[i + 1]
  min_len = min(len(w1), len(w2))
  if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
      return ""
  for j in range(min_len):
      if w1[j] != w2[j]:
          adj[w1[j]].add(w2[j])
          break

Objective

To build a graph where each character points to characters that must come after it, based on the first differing character between adjacent words.

Key Insight

Comparing adjacent words reveals the minimal necessary ordering constraints. The first position where two words differ determines a direct precedence edge from the character in the first word to the character in the second. This approach avoids over-constraining the graph and ensures only valid edges are added. Detecting the invalid prefix case here prevents futile graph construction.

Interview Quick-Check

Core Logic

Build adjacency sets for each character by comparing adjacent words and adding an edge from the first differing character in the first word to that in the second.

Common Pitfalls & Bugs

Failing to detect the invalid prefix case where a longer word precedes its prefix leads to incorrect results or infinite loops.

State & Boundaries

Stop comparing characters at the first difference to avoid adding incorrect edges.

2

Perform DFS-Based Topological Sort with Cycle Detection

To traverse the graph depth-first, detect cycles, and build the character order in reverse postorder.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 12 Critical lines interviewers watch for.

Line 8 Critical

if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:

Check for invalid prefix case where longer word precedes its prefix.

This condition violates lexicographical order rules, so detecting it early allows immediate termination with an empty string, preventing incorrect results.

Line 31 Critical

if dfs(c):

If DFS detects a cycle starting from this character, return empty string.

Cycle detection invalidates the ordering, so the algorithm must terminate early with no solution.

Line 9 Critical

return ""

Return empty string upon detecting invalid prefix ordering.

Returning immediately signals no valid character order exists due to contradictory input ordering.

Full line-by-line criticality + rationale for all 25 lines available on Pro.

Test Your Understanding

Why must the algorithm detect the invalid prefix case where a longer word precedes its prefix, and how does this affect the ordering?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Alien Dictionary from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Alien Dictionary drill

or drill a free problem

1	`class Solution:`
2	`def alienOrder(self, words: list[str]) -> str:`
3	`adj = { c: set() for w in words for c in w }`
4
5	`for i in range(len(words) - 1):`
6	`w1, w2 = words[i], words[i + 1]`
7	`min_len = min(len(w1), len(w2))`
8	`if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:`
9	`return ""`
10	`for j in range(min_len):`
11	`if w1[j] != w2[j]:`
12	`adj[w1[j]].add(w2[j])`
13	`break`
14
15	`visit = {}`
16	`res = []`
17
18	`def dfs(c):`
19	`if c in visit:`
20	`return visit[c]`
21
22	`visit[c] = True`
23	`for nei in adj[c]:`
24	`if dfs(nei):`
25	`return True`
26
27	`visit[c] = False`
28	`res.append(c)`
29
30	`for c in adj:`
31	`if dfs(c):`
32	`return ""`
33
34	`return "".join(res[::-1])`

3	`adj = { c: set() for w in words for c in w }`
5	`for i in range(len(words) - 1):`
6	`w1, w2 = words[i], words[i + 1]`
7	`min_len = min(len(w1), len(w2))`
8	`if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:`
9	`return ""`
10	`for j in range(min_len):`
11	`if w1[j] != w2[j]:`
12	`adj[w1[j]].add(w2[j])`
13	`break`