Alien Dictionary

▶

Steps

setup

Initialize graph and in-degree map

Create an empty graph and initialize in-degree counts for every unique character found in all words.

💡 This step sets up the data structures needed to track character dependencies and how many prerequisites each character has.

Line:

graph = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}

💡 All characters start with zero in-degree and no edges, ready for dependency discovery.

compare

Compare first word pair: 'wrt' and 'wrf'

Compare characters of 'wrt' and 'wrf' to find the first differing character and establish an edge.

💡 Comparing adjacent words reveals ordering constraints between characters.

Line:

w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))

💡 We prepare to compare characters up to the shortest word length.

compare

Find first differing character at index 2: 't' vs 'f'

At character index 2, 't' in 'wrt' differs from 'f' in 'wrf', so add edge t -> f and increment in-degree of 'f'.

💡 This edge means 't' comes before 'f' in the alien dictionary order.

Line:

if w1[j] != w2[j]:
  if w2[j] not in graph[w1[j]]:
    graph[w1[j]].add(w2[j])
    in_degree[w2[j]] += 1
  break

💡 Edges represent direct ordering constraints between characters.

compare

Compare second word pair: 'wrf' and 'er'

Compare 'wrf' and 'er' character by character to find the first difference and add an edge.

💡 Comparing these words will reveal another ordering constraint.

Line:

w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))

💡 We prepare to compare characters up to the shortest word length again.

compare

Find first differing character at index 0: 'w' vs 'e'

At index 0, 'w' differs from 'e', so add edge w -> e and increment in-degree of 'e'.

💡 This edge means 'w' comes before 'e' in the alien dictionary order.

Line:

if w1[j] != w2[j]:
  if w2[j] not in graph[w1[j]]:
    graph[w1[j]].add(w2[j])
    in_degree[w2[j]] += 1
  break

💡 Edges accumulate to form the partial order graph.

compare

Compare third word pair: 'er' and 'ett'

Compare 'er' and 'ett' to find the first differing character and add an edge.

💡 This comparison will add more ordering constraints.

Line:

w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))

💡 We prepare to compare characters up to the shortest word length again.

compare

Find first differing character at index 1: 'r' vs 't'

At index 1, 'r' differs from 't', so add edge r -> t and increment in-degree of 't'.

💡 This edge means 'r' comes before 't' in the alien dictionary order.

Line:

if w1[j] != w2[j]:
  if w2[j] not in graph[w1[j]]:
    graph[w1[j]].add(w2[j])
    in_degree[w2[j]] += 1
  break

💡 Edges build the dependency graph incrementally.

compare

Compare fourth word pair: 'ett' and 'rftt'

Compare 'ett' and 'rftt' to find the first differing character and add an edge.

💡 This comparison will add the last ordering constraint.

Line:

w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))

💡 We prepare to compare characters up to the shortest word length again.

compare

Find first differing character at index 0: 'e' vs 'r'

At index 0, 'e' differs from 'r', so add edge e -> r and increment in-degree of 'r'.

💡 This edge means 'e' comes before 'r' in the alien dictionary order.

Line:

if w1[j] != w2[j]:
  if w2[j] not in graph[w1[j]]:
    graph[w1[j]].add(w2[j])
    in_degree[w2[j]] += 1
  break

💡 The graph now fully represents all ordering constraints from the input.

setup

Initialize queue with zero in-degree characters

Add all characters with zero in-degree to the queue to start BFS topological sort.

💡 Characters with zero in-degree have no prerequisites and can appear first in the order.

Line:

queue = deque([c for c in in_degree if in_degree[c] == 0])

💡 Queue initialization identifies starting points for BFS traversal.

traverse

Process 'w' from queue

Dequeue 'w', append it to output, and reduce in-degree of its neighbors.

💡 Processing a character means confirming its position and updating dependencies.

Line:

c = queue.popleft()
output.append(c)
for nei in graph[c]:
  in_degree[nei] -= 1
  if in_degree[nei] == 0:
    queue.append(nei)

💡 When a neighbor's in-degree hits zero, it becomes ready to process.

traverse

Process 'e' from queue

Dequeue 'e', append it to output, and reduce in-degree of its neighbors.

💡 Continue BFS by processing the next character with zero in-degree.

Line:

c = queue.popleft()
output.append(c)
for nei in graph[c]:
  in_degree[nei] -= 1
  if in_degree[nei] == 0:
    queue.append(nei)

💡 Processing 'e' unlocks 'r' for processing next.

traverse

Process 'r' from queue

Dequeue 'r', append it to output, and reduce in-degree of its neighbors.

💡 Continue BFS traversal by processing 'r'.

Line:

c = queue.popleft()
output.append(c)
for nei in graph[c]:
  in_degree[nei] -= 1
  if in_degree[nei] == 0:
    queue.append(nei)

💡 Processing 'r' unlocks 't' for processing next.

traverse

Process 't' from queue

Dequeue 't', append it to output, and reduce in-degree of its neighbors.

💡 Continue BFS traversal by processing 't'.

Line:

c = queue.popleft()
output.append(c)
for nei in graph[c]:
  in_degree[nei] -= 1
  if in_degree[nei] == 0:
    queue.append(nei)

💡 Processing 't' unlocks 'f' for processing next.

traverse

Process 'f' from queue

Dequeue 'f' and append it to output. 'f' has no neighbors to update.

💡 Processing the last character completes the BFS traversal.

Line:

c = queue.popleft()
output.append(c)
for nei in graph[c]:
  in_degree[nei] -= 1
  if in_degree[nei] == 0:
    queue.append(nei)

💡 All characters processed, topological order found.

prune

Check if all characters processed

Verify if the output length matches the number of unique characters to confirm no cycle exists.

💡 If lengths differ, a cycle or invalid input exists and no valid order can be returned.

Line:

if len(output) != len(in_degree):
  return ""

💡 Successful topological sort means a valid alien dictionary order is found.

reconstruct

Return final alien dictionary order

Join the characters in output to form the final alien dictionary string.

💡 This final step produces the answer from the BFS traversal result.

Line:

return ''.join(output)

💡 The final string represents the inferred character order.

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)  # STEP 1
    in_degree = {c: 0 for word in words for c in word}  # STEP 1

    for i in range(len(words) - 1):  # STEP 2,4,6,8
        w1, w2 = words[i], words[i+1]  # STEP 2,4,6,8
        min_len = min(len(w1), len(w2))  # STEP 2,4,6,8
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:  # prefix invalid case
            return ""  # Not triggered in this example
        for j in range(min_len):  # STEP 3,5,7,9
            if w1[j] != w2[j]:  # STEP 3,5,7,9
                if w2[j] not in graph[w1[j]]:  # STEP 3,5,7,9
                    graph[w1[j]].add(w2[j])  # STEP 3,5,7,9
                    in_degree[w2[j]] += 1  # STEP 3,5,7,9
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])  # STEP 10
    output = []  # STEP 10

    while queue:  # STEP 11-15
        c = queue.popleft()  # STEP 11-15
        output.append(c)  # STEP 11-15
        for nei in graph[c]:  # STEP 11-15
            in_degree[nei] -= 1  # STEP 11-15
            if in_degree[nei] == 0:  # STEP 11-15
                queue.append(nei)  # STEP 11-15

    if len(output) != len(in_degree):  # STEP 16
        return ""
    return ''.join(output)  # STEP 17

if __name__ == '__main__':
    words = ["wrt", "wrf", "er", "ett", "rftt"]
    print(alienOrder(words))

📊

Alien Dictionary - Watch the Algorithm Execute, Step by Step

Watching each step reveals how character order is inferred from word pairs and how cycles or invalid cases are detected early.

setup

wrt

0

wrf

1

er

2

ett

3

rftt

4

Result: {"graph":{},"in_degree":{"w":0,"r":0,"t":0,"f":0,"e":0}}

compare

j

wrt

0

wrf

1

er

2

ett

3

rftt

4

Result: {"graph":{},"in_degree":{"w":0,"r":0,"t":0,"f":0,"e":0}}

compare

i

wrt

0

wrf

1

j

er

2

ett

3

rftt

4

Result: {"graph":{"t":["f"]},"in_degree":{"w":0,"r":0,"t":0,"f":1,"e":0}}

compare

j

wrt

0

i

wrf

1

er

2

ett

3

rftt

4

Result: {"graph":{"t":["f"]},"in_degree":{"w":0,"r":0,"t":0,"f":1,"e":0}}

compare

j

wrt

0

i

wrf

1

er

2

ett

3

rftt

4

Result: {"graph":{"t":["f"],"w":["e"]},"in_degree":{"w":0,"r":0,"t":0,"f":1,"e":1}}

compare

j

wrt

0

wrf

1

i

er

2

ett

3

rftt

4

Result: {"graph":{"t":["f"],"w":["e"]},"in_degree":{"w":0,"r":0,"t":0,"f":1,"e":1}}

compare

wrt

0

j

wrf

1

i

er

2

ett

3

rftt

4

Result: {"graph":{"t":["f"],"w":["e"],"r":["t"]},"in_degree":{"w":0,"r":0,"t":1,"f":1,"e":1}}

compare

j

wrt

0

wrf

1

er

2

i

ett

3

rftt

4

Result: {"graph":{"t":["f"],"w":["e"],"r":["t"]},"in_degree":{"w":0,"r":0,"t":1,"f":1,"e":1}}

compare

j

wrt

0

wrf

1

er

2

i

ett

3

rftt

4

Result: {"graph":{"t":["f"],"w":["e"],"r":["t"],"e":["r"]},"in_degree":{"w":0,"r":1,"t":1,"f":1,"e":1}}

setup

queue_front

w

0

r

1

t

2

f

3

e

4

Result: {"queue":["w"],"output":[]}

move_left

queue_front

w

0

e

1

Result: {"queue":["e"],"output":["w"],"in_degree":{"w":0,"r":1,"t":1,"f":1,"e":0}}

move_left

queue_front

e

0

r

1

Result: {"queue":["r"],"output":["w","e"],"in_degree":{"w":0,"r":0,"t":1,"f":1,"e":0}}

move_left

queue_front

r

0

t

1

Result: {"queue":["t"],"output":["w","e","r"],"in_degree":{"w":0,"r":0,"t":0,"f":1,"e":0}}

move_left

queue_front

t

0

f

1

Result: {"queue":["f"],"output":["w","e","r","t"],"in_degree":{"w":0,"r":0,"t":0,"f":0,"e":0}}

move_left

f

0

Result: {"queue":[],"output":["w","e","r","t","f"],"in_degree":{"w":0,"r":0,"t":0,"f":0,"e":0}}

prune

w

0

e

1

r

2

t

3

f

4

Result: {"output":["w","e","r","t","f"]}

record

w

0

e

1

r

2

t

3

f

4

Result: "wertf"

Key Takeaways

✓ The algorithm builds a directed graph of character dependencies by comparing adjacent words.

This insight is hard to see from code alone because the graph construction is implicit and involves nested loops.

✓ In-degree counts track how many prerequisites each character has, enabling BFS to find the order.

Visualizing in-degree updates clarifies why characters enter the queue only when all dependencies are resolved.

✓ The BFS topological sort processes characters in order, revealing the alien dictionary order or detecting cycles.

Seeing the queue and output evolve step-by-step makes the topological sort logic concrete and intuitive.

Practice

1. Given a list of unique words, you need to find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] forms a palindrome. Which approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Brute force nested loops checking all pairs and verifying palindrome by concatenation

B. Building a Trie of reversed words and tracking palindrome suffixes to find pairs efficiently

C. Dynamic programming to find palindromic substrings and then pairing indices accordingly

D. Greedy approach by sorting words and pairing those with matching prefixes and suffixes

Solution

1. Step 1: Understand brute force limitations

   Brute force checks all pairs, resulting in O(n^2 * k) time, which is inefficient for large n.

2. Step 2: Recognize Trie-based optimization

   Building a Trie of reversed words allows prefix matching and palindrome suffix tracking, reducing redundant checks and achieving O(n * k^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie-based approach is known optimal for palindrome pairs [OK]

Hint: Trie with palindrome suffixes optimizes palindrome pair search [OK]

Common Mistakes:

• Assuming brute force is acceptable for large inputs
• Confusing palindrome substring DP with pair finding
• Believing greedy prefix-suffix matching suffices

2. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n (number of balloons)?

medium

A. O(n * 2^n)

B. O(n^2)

C. O(n^3)

D. O(n^4)

Solution

1. Step 1: Identify nested loops in the bottom-up DP

   There are three nested loops: length (up to n), left (up to n), and i (between left and right), each up to n.

2. Step 2: Calculate total operations

   Multiplying the three loops gives O(n^3) time complexity. The dp table is size n^2, so space is O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Three nested loops over n -> O(n^3) [OK]

Hint: Three nested loops over n cause cubic time [OK]

Common Mistakes:

• Confusing with exponential brute force
• Forgetting the third loop
• Assuming quadratic time

3. Consider the following buggy code snippet for the optimal median of two sorted arrays. Which line contains the subtle bug that can cause incorrect median calculation or runtime error?

medium

A. Line 10: max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]

B. Line 7: i = (low + high) // 2

C. Line 17: elif max_left_nums1 > min_right_nums2:

D. Line 2: if len(nums1) < len(nums2): nums1, nums2 = nums2, nums1

Solution

1. Step 1: Check array swap condition

   The code swaps arrays only if len(nums1) < len(nums2), which is incorrect. It should swap if nums1 is larger to ensure binary search on smaller array.

2. Step 2: Consequences of wrong swap

   Without correct swap, binary search range can be large, causing inefficiency or index errors.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Swap condition reversed causes subtle bugs [OK]

Hint: Swap arrays so binary search is on smaller one [OK]

Common Mistakes:

• Swapping arrays incorrectly or not at all
• Off-by-one errors in partition indices
• Incorrect median calculation for odd/even lengths

4. Examine the following snippet from an implementation of the optimal Word Search II solution. Which line contains a subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line where curr_node.word is not set to null after found

B. Line where board[r][c] is set to '#'

C. Line where curr_node.word is appended to res

D. Line where backtrack is recursively called on neighbors

Solution

1. Step 1: Identify purpose of setting curr_node.word to None

   This prevents adding the same word multiple times by marking it as found.

2. Step 2: Analyze effect of missing this line

   Without setting curr_node.word to None, duplicates can be appended and redundant searches occur, possibly causing inefficiency or infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing word removal after found causes duplicates [OK]

Hint: Mark found words None to avoid duplicates [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not pruning found words
• Incorrect recursion boundaries

5. Suppose the problem is modified so that the path can reuse nodes multiple times (cycles allowed). Which of the following statements about adapting the maximum path sum algorithm is correct?

hard

A. The existing recursive approach works without changes because it already considers all paths.

B. The problem reduces to finding the maximum sum cycle in a graph, which can be solved by the same recursion.

C. We can simply remove the max(..., 0) checks to allow negative gains and reuse nodes.

D. We must detect and avoid cycles, possibly using memoization or graph algorithms, since the tree is no longer acyclic.

Solution

1. Step 1: Recognize that allowing node reuse introduces cycles, so the structure is no longer a tree.

   The original recursion assumes acyclic structure and no repeated nodes.

2. Step 2: Understand that to handle cycles, the algorithm must detect and avoid infinite recursion, typically via memoization or graph cycle detection.

   Standard tree recursion breaks down without cycle checks.

3. Step 3: Note that removing max(..., 0) or reusing nodes without cycle detection leads to infinite loops or incorrect sums.

   Maximum sum cycle detection is a different problem requiring graph algorithms.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Cycle detection and memoization are necessary for graphs with cycles [OK]

Hint: Cycles require cycle detection and memoization [OK]

Common Mistakes:

• Assuming tree recursion works unchanged
• Removing zero cutoff to allow reuse
• Confusing max path sum with max cycle sum