Alien Dictionary (Infer Character Order)

▶

Steps

setup

Initialize graph and in-degree map

Create nodes for each unique character and initialize their in-degree to zero. No edges exist yet.

💡 This sets up the framework to track dependencies between characters.

Line:

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

💡 All characters are known upfront, even before we know their order.

expand

Compare 'wrt' and 'wrf' to add edge 't' -> 'f'

Compare characters of 'wrt' and 'wrf' until a difference is found at index 2: 't' vs 'f'. Add edge from 't' to 'f' and increment in-degree of 'f'.

💡 This reveals that 't' must come before 'f' in the alien dictionary.

Line:

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

💡 Edges represent ordering constraints derived from word comparisons.

expand

Compare 'wrf' and 'er' to add edge 'w' -> 'e'

Compare 'wrf' and 'er' and find first difference at index 0: 'w' vs 'e'. Add edge from 'w' to 'e' and increment in-degree of 'e'.

💡 This means 'w' must come before 'e'.

Line:

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

💡 Each edge encodes a direct ordering between two characters.

expand

Compare 'er' and 'ett' to add edge 'r' -> 't'

Compare 'er' and 'ett' and find first difference at index 1: 'r' vs 't'. Add edge from 'r' to 't' and increment in-degree of 't'.

💡 This means 'r' must come before 't'.

Line:

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

💡 Edges chain dependencies, building a partial order.

expand

Compare 'ett' and 'rftt' to add edge 'e' -> 'r'

Compare 'ett' and 'rftt' and find first difference at index 0: 'e' vs 'r'. Add edge from 'e' to 'r' and increment in-degree of 'r'.

💡 This means 'e' must come before 'r'.

Line:

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

💡 The graph now has a cycle-free chain of dependencies.

setup

Initialize queue with zero in-degree nodes

Add all characters with zero in-degree to the queue. These characters have no prerequisites and can start the order.

💡 Queue initialization is critical to start topological sorting.

Line:

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

💡 Characters with zero in-degree are the starting points for ordering.

traverse

Process node 'w' from queue

Dequeue 'w' and add it to the order. Mark 'w' as done. Decrement in-degree of its neighbor 'e'.

💡 Processing 'w' means we have placed it in the order and can update dependencies.

Line:

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

💡 'w' has no prerequisites and unlocks 'e' by reducing its in-degree.

expand

Add 'e' to queue after in-degree zero

After decrementing, 'e' has zero in-degree and is added to the queue, ready to be processed next.

💡 Adding 'e' to the queue means it can now be placed in the order.

Line:

if in_degree[nei] == 0:
  queue.append(nei)

💡 Queue dynamically updates as dependencies are resolved.

traverse

Process node 'e' from queue

Dequeue 'e', add to order, mark done, and decrement in-degree of neighbor 'r'.

💡 Processing 'e' unlocks 'r' by reducing its in-degree.

Line:

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

💡 Processing nodes in order respects dependencies.

expand

Add 'r' to queue after in-degree zero

After decrementing, 'r' has zero in-degree and is added to the queue.

💡 This means 'r' can now be placed in the order.

Line:

if in_degree[nei] == 0:
  queue.append(nei)

💡 Queue updates as dependencies are resolved.

traverse

Process node 'r' from queue

Dequeue 'r', add to order, mark done, and decrement in-degree of neighbor 't'.

💡 Processing 'r' unlocks 't' by reducing its in-degree.

Line:

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

💡 Processing respects the partial order constraints.

expand

Add 't' to queue after in-degree zero

After decrementing, 't' has zero in-degree and is added to the queue.

💡 This means 't' can now be placed in the order.

Line:

if in_degree[nei] == 0:
  queue.append(nei)

💡 Queue dynamically reflects resolved dependencies.

traverse

Process node 't' from queue

Dequeue 't', add to order, mark done, and decrement in-degree of neighbor 'f'.

💡 Processing 't' unlocks 'f' by reducing its in-degree.

Line:

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

💡 Processing nodes in order respects all dependencies.

expand

Add 'f' to queue after in-degree zero

After decrementing, 'f' has zero in-degree and is added to the queue.

💡 This means 'f' can now be placed in the order.

Line:

if in_degree[nei] == 0:
  queue.append(nei)

💡 Queue reflects the final character ready to be processed.

traverse

Process node 'f' from queue

Dequeue 'f', add to order, mark done. 'f' has no neighbors to update.

💡 Processing 'f' completes the ordering of all characters.

Line:

c = queue.popleft()
order.append(c)

💡 All characters have been processed respecting dependencies.

reconstruct

Check if all characters processed and return order

Verify that the order contains all characters. Since it does, join and return the order string.

💡 This confirms no cycles exist and the order is valid.

Line:

if len(order) != len(in_degree):
  return ""
return "".join(order)

💡 Topological sort successfully inferred the alien dictionary 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-5
        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]:  # STEP 2-5
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

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

    if len(order) != len(in_degree):  # STEP 16
        return ""
    return "".join(order)

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

📊

Alien Dictionary (Infer Character Order) - Watch the Algorithm Execute, Step by Step

Watching each step of the topological sort reveals how character order is inferred from word comparisons, making the abstract concept concrete.

Visiting: none

w

r

t

f

e

Visiting: none

w

r

t

f

e

Visiting: none

w

r

t

f

e

Visiting: none

w

r

t

f

e

Visiting: none

w

r

t

f

e

Visiting: none

w

r

t

f

e

Queue / Stack

w

Visiting: w

w

r

t

f

e

Visiting: none

w

r

t

f

e

Queue / Stack

e

Visiting: e

w

r

t

f

e

Visiting: none

w

r

t

f

e

Queue / Stack

r

Visiting: r

w

r

t

f

e

Visiting: none

w

r

t

f

e

Queue / Stack

t

Visiting: t

w

r

t

f

e

Visiting: none

w

r

t

f

e

Queue / Stack

f

Visiting: f

w

r

t

f

e

Visiting: none

w

e

r

t

f

Key Takeaways

✓ Topological sorting reveals the order of characters by processing nodes with zero in-degree first.

This insight is hard to see from code alone because the dynamic update of in-degree and queue is abstract without visualization.

✓ Edges represent direct ordering constraints inferred from the first differing characters between adjacent words.

Visualizing edges helps understand how pairwise word comparisons build a global order.

✓ The queue dynamically changes as characters become ready to be processed, reflecting the resolution of dependencies.

Seeing the queue contents change step-by-step clarifies how the algorithm progresses through the graph.

Practice

1. You need to construct a matrix where each row and column must satisfy a set of ordering constraints given as pairs (a before b). Which algorithmic approach best guarantees a valid construction if one exists?

easy

A. Greedy approach that places elements in the earliest available position without checking for cycles

B. Topological sort on the dependency graph to determine valid positions for each element

C. Dynamic programming to find the longest increasing subsequence of elements based on constraints

D. Divide and conquer by splitting constraints into smaller independent sets and merging results

Solution

1. Step 1: Understand the problem as ordering with dependencies

   The problem requires respecting partial order constraints, which naturally maps to a directed graph where edges represent "before" relations.

2. Step 2: Identify the algorithm that handles partial orders and detects cycles

   Topological sort is the standard algorithm to order nodes in a DAG respecting dependencies and detect cycles if no valid order exists.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort guarantees a valid order or detects impossibility [OK]

Hint: Partial order constraints -> topological sort [OK]

Common Mistakes:

• Assuming greedy placement always works
• Confusing with DP longest subsequence
• Ignoring cycle detection

2. You are given a directed graph where each node has a color represented by a lowercase letter. The goal is to find the maximum number of occurrences of any single color along any path in the graph. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy traversal selecting the most frequent color at each step

B. Dijkstra's algorithm to find shortest paths weighted by color frequency

C. Topological sort combined with iterative dynamic programming to track color counts

D. Simple DFS exploring all paths without memoization

Solution

1. Step 1: Understand problem constraints and graph properties

   The problem requires tracking maximum color counts along paths in a directed graph, which may contain dependencies and cycles.

2. Step 2: Identify suitable algorithm

   Topological sort linearizes nodes respecting dependencies, enabling iterative DP to accumulate color counts efficiently without redundant recomputation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Topological sort + DP handles dependencies and cycles correctly [OK]

Hint: Topological sort enables DP on DAGs [OK]

Common Mistakes:

• Assuming greedy or simple DFS suffices without cycle detection

3. Consider the following code snippet implementing the optimal solution for the largest color value in a directed graph. Given colors = "abaca" and edges = [[0,1],[0,2],[2,3],[3,4]], what is the value of max_color_value after processing all nodes?

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace dp for node 0 (color 'a')

   dp[0]['a'] = 1, max_color_value = 1

2. Step 2: Propagate to nodes 1 and 2

   Node 1 (color 'b'): dp[1]['a'] = 1, dp[1]['b'] = 1; Node 2 (color 'a'): dp[2]['a'] = 2, max_color_value = 2

3. Step 3: Propagate to node 3 (color 'c')

   dp[3]['a'] = 2, dp[3]['c'] = 1, max_color_value = 2

4. Step 4: Propagate to node 4 (color 'a')

   dp[4]['a'] = 3, max_color_value = 3

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Maximum color count along path is 3 for 'a' [OK]

Hint: Track dp updates per node carefully [OK]

Common Mistakes:

• Off-by-one in dp increments or max updates

4. Consider the following Python code implementing the optimal approach for minimum semesters. Given n = 3 and relations = [[1,3],[2,3]], what is the value of semester returned by the function?

from collections import deque, defaultdict

def min_semesters_optimal(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    semester = 0
    processed = 0

    while queue:
        semester += 1
        for _ in range(len(queue)):
            course = queue.popleft()
            processed += 1
            for nei in graph[course]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

    return semester if processed == n else -1

print(min_semesters_optimal(3, [[1,3],[2,3]]))

easy

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Initialize graph and indegree

   Courses 1 and 2 have indegree 0, course 3 has indegree 2.

2. Step 2: Process BFS levels

   Semester 1: process courses 1 and 2 (both indegree 0), decrement indegree of 3 twice -> indegree[3] becomes 0, add 3 to queue. Semester 2: process course 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two BFS levels -> 2 semesters [OK]

Hint: Courses with zero indegree processed per semester [OK]

Common Mistakes:

• Counting each course as a separate semester
• Off-by-one error in semester increment
• Returning -1 incorrectly when all courses processed

5. What is the time complexity of the optimal BFS-based topological sort algorithm for the Parallel Courses problem, given n courses and m prerequisite relations?

medium

A. O(n + m) because each node and edge is processed once in BFS

B. O(m^2) because updating indegrees requires scanning all edges repeatedly

C. O(n * m) because for each course you process all edges

D. O(n^2) because in the worst case all courses depend on all others

Solution

1. Step 1: Analyze graph traversal

   Each course (node) is enqueued and dequeued at most once; each edge is visited once when decrementing indegree.

2. Step 2: Combine node and edge processing

   Total operations proportional to number of nodes plus edges -> O(n + m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in nodes and edges [OK]

Hint: Each edge and node processed once in BFS [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing indegree updates as repeated scans
• Assuming dense graph means O(n^2) always