Approach Summary
Extract precedence rules by comparing adjacent words at the first differing character, build a directed graph (DAG), and run topological sort with cycle detection.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: BFS / Kahn's Algorithm (In-Degree Array) | O(C) | O(V + E) = O(1) | Extract precedence edges from adjacent words and apply BFS topological sorting with in-degrees. |
| 2 Approach 2: DFS Post-Order Topological Sort (Optimal) | O(C) | O(V + E) = O(1) | Run depth-first search recording visited status and pushing nodes to a stack upon return. |
Step 1: Baseline
Approach 1: BFS / Kahn's Algorithm (In-Degree Array)
Time: O(C)
Space: O(V + E) = O(1)
Compare adjacent words dict[i] and dict[i+1]. The first differing character defines a directed edge `c1 -> c2`. We calculate in-degrees for all characters. Enqueue characters with in-degree 0. While the queue is non-empty, pop a character, append it to the result, and decrement neighbors in-degrees. If the result length matches the total number of unique characters, return the string; otherwise, a cycle was detected, making a valid ordering impossible.
Approach 1: BFS / Kahn's Algorithm (In-Degree Array) Implementation
Approach 1: BFS / Kahn's Algorithm (In-Degree Array)
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> adj = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
for (String w : words) {
for (char c : w.toCharArray()) {
adj.putIfAbsent(c, new HashSet<>());
inDegree.putIfAbsent(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i], w2 = words[i + 1];
if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
char c1 = w1.charAt(j), c2 = w2.charAt(j);
if (c1 != c2) {
if (!adj.get(c1).contains(c2)) {
adj.get(c1).add(c2);
inDegree.put(c2, inDegree.get(c2) + 1);
}
break;
}
}
}
Queue<Character> queue = new LinkedList<>();
for (char c : inDegree.keySet()) {
if (inDegree.get(c) == 0) queue.offer(c);
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
sb.append(c);
for (char neighbor : adj.get(c)) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) == 0) queue.offer(neighbor);
}
}
return sb.length() == inDegree.size() ? sb.toString() : "";
}
}class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> adj;
unordered_map<char, int> inDegree;
for (const auto& w : words) {
for (char c : w) {
adj[c];
inDegree[c] = 0;
}
}
for (size_t i = 0; i < words.size() - 1; i++) {
const string& w1 = words[i];
const string& w2 = words[i + 1];
if (w1.size() > w2.size() && w1.compare(0, w2.size(), w2) == 0) return "";
for (size_t j = 0; j < min(w1.size(), w2.size()); j++) {
if (w1[j] != w2[j]) {
if (adj[w1[j]].insert(w2[j]).second) {
inDegree[w2[j]]++;
}
break;
}
}
}
queue<char> q;
for (auto& [c, deg] : inDegree) {
if (deg == 0) q.push(c);
}
string res = "";
while (!q.empty()) {
char c = q.front(); q.pop();
res += c;
for (char next : adj[c]) {
if (--inDegree[next] == 0) q.push(next);
}
}
return res.size() == inDegree.size() ? res : "";
}
};from collections import defaultdict, deque
def alien_order(words: list[str]) -> str:
adj = {c: set() for w in words for c in w}
in_degree = {c: 0 for c in adj}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
if len(w1) > len(w2) and w1.startswith(w2):
return ""
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in adj[c1]:
adj[c1].add(c2)
in_degree[c2] += 1
break
q = deque([c for c in in_degree if in_degree[c] == 0])
res = []
while q:
c = q.popleft()
res.append(c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return "".join(res) if len(res) == len(in_degree) else ""function alienOrder(words) {
const adj = new Map();
const inDegree = new Map();
for (const w of words) {
for (const c of w) {
if (!adj.has(c)) adj.set(c, new Set());
if (!inDegree.has(c)) inDegree.set(c, 0);
}
}
for (let i = 0; i < words.length - 1; i++) {
const w1 = words[i], w2 = words[i + 1];
if (w1.length > w2.length && w1.startsWith(w2)) return "";
for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
if (w1[j] !== w2[j]) {
if (!adj.get(w1[j]).has(w2[j])) {
adj.get(w1[j]).add(w2[j]);
inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
}
break;
}
}
}
const queue = [];
for (const [c, deg] of inDegree.entries()) {
if (deg === 0) queue.push(c);
}
const res = [];
while (queue.length > 0) {
const c = queue.shift();
res.push(c);
for (const next of adj.get(c)) {
inDegree.set(next, inDegree.get(next) - 1);
if (inDegree.get(next) === 0) queue.push(next);
}
}
return res.length === inDegree.size ? res.join("") : "";
} Step 2: Most Optimized
Approach 2: DFS Post-Order Topological Sort (Optimal)
Time: O(C)
Space: O(V + E) = O(1)
Construct adjacency lists for all k alphabet characters. Use a recursion stack and visited array. For each unvisited node, recursively traverse its neighbors. Once all descendants are visited, push the current vertex onto the stack. Unwinding the stack gives the reverse post-order, which is the topological sequence.
Approach 2: DFS Post-Order Topological Sort (Optimal) Implementation
Approach 2: DFS Post-Order Topological Sort (Optimal)
class Solution {
public void topologicalSort(int v, List<List<Integer>> adj, boolean visited[], Stack<Integer> stack) {
visited[v] = true;
List<Integer> neighbors = adj.get(v);
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
topologicalSort(neighbor, adj, visited, stack);
}
}
stack.add(v);
}
public String findOrder(String[] dict, int n, int k) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < k; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
String s1 = dict[i];
String s2 = dict[i + 1];
int len = Math.min(s1.length(), s2.length());
for (int ptr = 0; ptr < len; ptr++) {
if (s1.charAt(ptr) != s2.charAt(ptr)) {
adj.get(s1.charAt(ptr) - 'a').add(s2.charAt(ptr) - 'a');
break;
}
}
}
Stack<Integer> stack = new Stack<>();
boolean visited[] = new boolean[k];
for (int i = 0; i < k; i++) {
if (!visited[i]) {
topologicalSort(i, adj, visited, stack);
}
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append((char) (stack.pop() + (int) ('a')));
}
return result.toString();
}
}class Solution {
public:
void topologicalSort(int v, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
visited[v] = true;
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
topologicalSort(neighbor, adj, visited, st);
}
}
st.push(v);
}
string findOrder(string dict[], int n, int k) {
vector<vector<int>> adj(k);
for (int i = 0; i < n - 1; i++) {
string s1 = dict[i];
string s2 = dict[i + 1];
int len = min(s1.length(), s2.length());
for (int ptr = 0; ptr < len; ptr++) {
if (s1[ptr] != s2[ptr]) {
adj[s1[ptr] - 'a'].push_back(s2[ptr] - 'a');
break;
}
}
}
stack<int> st;
vector<bool> visited(k, false);
for (int i = 0; i < k; i++) {
if (!visited[i]) {
topologicalSort(i, adj, visited, st);
}
}
string result = "";
while (!st.empty()) {
result += (char)(st.top() + 'a');
st.pop();
}
return result;
}
};def find_order(dict_words: list[str], n: int, k: int) -> str:
adj = [[] for _ in range(k)]
for i in range(n - 1):
s1, s2 = dict_words[i], dict_words[i + 1]
for ptr in range(min(len(s1), len(s2))):
if s1[ptr] != s2[ptr]:
adj[ord(s1[ptr]) - ord('a')].append(ord(s2[ptr]) - ord('a'))
break
visited = [False] * k
stack = []
def dfs(v):
visited[v] = True
for neighbor in adj[v]:
if not visited[neighbor]:
dfs(neighbor)
stack.append(v)
for i in range(k):
if not visited[i]:
dfs(i)
return "".join(chr(c + ord('a')) for c in reversed(stack))function findOrder(dict, n, k) {
const adj = Array.from({ length: k }, () => []);
for (let i = 0; i < n - 1; i++) {
const s1 = dict[i], s2 = dict[i + 1];
for (let ptr = 0; ptr < Math.min(s1.length, s2.length); ptr++) {
if (s1[ptr] !== s2[ptr]) {
adj[s1.charCodeAt(ptr) - 97].push(s2.charCodeAt(ptr) - 97);
break;
}
}
}
const visited = new Array(k).fill(false);
const stack = [];
function dfs(v) {
visited[v] = true;
for (const neighbor of adj[v]) {
if (!visited[neighbor]) dfs(neighbor);
}
stack.push(v);
}
for (let i = 0; i < k; i++) {
if (!visited[i]) dfs(i);
}
let res = "";
while (stack.length > 0) {
res += String.fromCharCode(stack.pop() + 97);
}
return res;
}Edge Cases to Watch
- Invalid prefix ordering: e.g. ["abc", "ab"] where the second word is a prefix of the first (returns "")
- Cycles in precedence: e.g. a -> b and b -> a (returns "")
- Single character or single word dictionary
- Disconnected graph components (any valid topological order among disjoint sets is accepted)
Algorithmic Pattern
View Pattern Guide →
Master the Topological Sort Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Topological Sort pattern.
Framework: Topological Sort • Interview Prep: Tested at FAANG •
Explore all Topological Sort problems & invariants →
How to Recognize This Pattern
- Derive character ordering from sorted foreign language dictionary
- DAG topological ordering with cycle check
Complexity Analysis
Time Complexity
O(C)
Space Complexity
O(1)
Tags
Array String Graph Topological Sort
Frequently Asked Questions
What is the optimal time and space complexity for Alien Dictionary?
The optimal solution for Alien Dictionary achieves O(C) runtime complexity and requires O(1) auxiliary space. Building the graph takes O(C) time where C is the total length of all words across the dictionary. Topological sort visits each unique character V and edge E once, taking O(V + E). Since the alphabet is bounded (at most 26 lowercase English letters), V ≤ 26 and E ≤ 26², so time is bounded by O(C) and space is O(1) bounded auxiliary space.
How do I identify that Alien Dictionary requires the Topological Sort pattern?
In technical interviews, look for key problem signals: Derive character ordering from sorted foreign language dictionary; DAG topological ordering with cycle check. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Topological Sort strategy.
What critical edge cases must be handled in Alien Dictionary?
Essential edge cases to verify include: Invalid prefix ordering: e.g. ["abc", "ab"] where the second word is a prefix of the first (returns ""); Cycles in precedence: e.g. a -> b and b -> a (returns ""); Single character or single word dictionary; Disconnected graph components (any valid topological order among disjoint sets is accepted). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Alien Dictionary?
Alien Dictionary is a Hard-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Google, Airbnb, Pinterest.