Alien Dictionary - Video Solutions

Problem Overview: You’re given a list of words already sorted according to an unknown alien language. The task is to recover the character ordering used by that language. If the ordering is invalid (cycle or prefix conflict), return an empty string.

Approach 1: Graph + Kahn’s Algorithm (Topological Sort using BFS) (Time: O(C + V + E), Space: O(V + E))

Model the problem as a directed graph where each character is a node. Compare adjacent words and find the first position where the characters differ. That difference defines an edge a → b, meaning character a comes before b. Track indegrees for each node, then apply breadth-first search with Kahn’s algorithm: push all nodes with indegree 0 into a queue and process them while reducing neighbors’ indegrees. If all characters are processed, the resulting order is valid. If not, a cycle exists and the dictionary is invalid.

This approach works well because topological sorting naturally models ordering constraints. The tricky part is validating prefix conflicts (e.g., "abc" before "ab"), which must immediately return an invalid result.

Approach 2: Graph + DFS Topological Sort (Time: O(C + V + E), Space: O(V + E))

Build the same directed graph using character precedence rules extracted from adjacent words. Instead of BFS, run a depth-first search on each node to perform topological ordering. Maintain three states for each node: unvisited, visiting, and visited. Encountering a node marked visiting indicates a cycle in the dependency graph, which makes the dictionary invalid.

During DFS, append nodes to a result list after exploring all neighbors. Reverse the final list to obtain the correct order. This version avoids maintaining an indegree array but requires careful cycle detection logic. It’s commonly used when recursion-based graph traversal is preferred.

Approach 3: Constraint Graph Construction from Adjacent Words (Time: O(C), Space: O(V))

The critical preprocessing step is extracting ordering constraints. Iterate through each adjacent pair of words and scan characters until the first mismatch. That mismatch produces the only valid ordering edge for that pair. Without this step, the graph would contain incorrect dependencies. The total comparison cost is proportional to the total characters C across all words.

This step is combined with either BFS or DFS topological sorting. Ensuring all characters appear in the graph—even those without edges—is necessary so isolated nodes are included in the final ordering.

Recommended for interviews: Use graph construction plus Kahn’s algorithm (BFS). Interviewers expect you to recognize this as a topological sort problem on a directed graph. Explaining the brute reasoning (extract ordering constraints from adjacent words) shows understanding, while implementing BFS with indegree tracking demonstrates strong graph fundamentals and clean cycle detection.