Alien Dictionary (Infer Character Order)

🎯

Alien Dictionary (Infer Character Order)

hardGRAPHFacebookAmazonGoogle

Imagine discovering the order of letters in an alien language by analyzing a sorted dictionary of alien words.

💡 This problem requires understanding how to infer order constraints from given data and then use graph algorithms to find a valid ordering. Beginners often struggle because it combines string processing with graph construction and topological sorting, which are distinct concepts.

📋

Problem Statement

Given a list of words sorted lexicographically in an alien language, derive the order of characters in that language. Return a string representing the characters in the correct order. If no valid order exists, return an empty string.

1 ≤ number of words ≤ 10^51 ≤ length of each word ≤ 100All characters are lowercase English lettersThe total length of all words combined does not exceed 10^6

💡

Example

Input["wrt","wrf","er","ett","rftt"]

Outputwertf

From 'wrt' and 'wrf', we infer 't' < 'f'. From 'wrt' and 'er', 'w' < 'e'. From 'er' and 'ett', 'r' < 't'. From 'ett' and 'rftt', 'e' < 'r'. Combining these gives the order 'w', 'e', 'r', 't', 'f'.

• Single word input → output is all unique characters in that word
• Words with prefix relationship where prefix word is longer → invalid order, output empty string
• Multiple disconnected components in graph → output concatenates all components in valid order
• Cycle in character order → output empty string

⚠️

Common Mistakes

Not handling prefix invalid case (e.g., 'abc' before 'ab')

Returns incorrect order or fails silently

✅ Check if longer word is prefix of shorter and return empty string

Not detecting cycles properly

Infinite loop or incorrect order returned

✅ Use visitation states in DFS or verify all nodes processed in BFS

Adding multiple edges for same character pair

Incorrect in-degree counts leading to wrong order

✅ Use sets to avoid duplicate edges

Not including all unique characters in the graph

Missing characters in final order

✅ Initialize graph and in-degree for all characters seen

Reversing order incorrectly in DFS approach

Output order is backwards

✅ Append characters postorder and reverse before returning

🧠

Brute Force (Compare All Pairs of Words)

💡 This approach exists to build intuition by directly comparing every pair of words to infer character order, but it is inefficient and impractical for large inputs.

Intuition

Compare every pair of adjacent words and find the first differing character to infer order. Then try to build the order by repeatedly applying these constraints.

Algorithm

1. Initialize an empty graph and in-degree map for all characters.
2. For each pair of adjacent words, compare characters to find the first difference and add a directed edge.
3. Perform a topological sort by repeatedly selecting characters with zero in-degree.
4. If a cycle is detected or ordering is incomplete, return empty string; else return the order.

💡 The main challenge is correctly building the graph and detecting cycles, which is not obvious at first glance.

</>

Code

from collections import defaultdict, deque

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

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        # Check prefix invalid case
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        for j in range(min_len):
            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

    # Topological sort
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        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):
        return ""
    return "".join(order)

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

Line Notes

graph = defaultdict(set)Initialize adjacency list to store edges from one char to another

in_degree = {c: 0 for word in words for c in word}Track how many incoming edges each character has

if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]Detect invalid prefix case where longer word comes before prefix

if w1[j] != w2[j]Find first differing character to infer order

graph[w1[j]].add(w2[j])Add directed edge from w1[j] to w2[j]

in_degree[w2[j]] += 1Increment in-degree of w2[j] because of new incoming edge

queue = deque([c for c in in_degree if in_degree[c] == 0])Start topological sort with characters having zero in-degree

while queue:Process characters in order, removing edges and updating in-degree

if len(order) != len(in_degree)If not all characters are included, a cycle exists

import java.util.*;

public class AlienDictionary {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();

        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.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];
            int minLen = Math.min(w1.length(), w2.length());
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    char c1 = w1.charAt(j), c2 = w2.charAt(j);
                    if (!graph.get(c1).contains(c2)) {
                        graph.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 order = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char nei : graph.get(c)) {
                inDegree.put(nei, inDegree.get(nei) - 1);
                if (inDegree.get(nei) == 0) queue.offer(nei);
            }
        }

        if (order.length() != inDegree.size()) return "";
        return order.toString();
    }

    public static void main(String[] args) {
        AlienDictionary sol = new AlienDictionary();
        String[] words = {"wrt","wrf","er","ett","rftt"};
        System.out.println(sol.alienOrder(words));
    }
}

Line Notes

Map<Character, Set<Character>> graph = new HashMap<>()Adjacency list to represent graph edges

Map<Character, Integer> inDegree = new HashMap<>()Track incoming edges count per character

if (w1.length() > w2.length() && w1.startsWith(w2))Detect invalid prefix ordering

if (w1.charAt(j) != w2.charAt(j))Find first differing character to infer order

graph.get(c1).add(c2)Add edge from c1 to c2

inDegree.put(c2, inDegree.get(c2) + 1)Increment in-degree of c2

for (char c : inDegree.keySet())Initialize queue with zero in-degree characters

while (!queue.isEmpty())Process characters in topological order

if (order.length() != inDegree.size())Check for cycles by comparing processed count

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <string>
using namespace std;

string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    unordered_map<char, int> inDegree;

    for (auto& word : words) {
        for (char c : word) {
            graph[c];
            inDegree[c] = 0;
        }
    }

    for (int i = 0; i < (int)words.size() - 1; i++) {
        string& w1 = words[i], &w2 = words[i + 1];
        int minLen = min(w1.size(), w2.size());
        if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen))
            return "";
        for (int j = 0; j < minLen; j++) {
            if (w1[j] != w2[j]) {
                if (graph[w1[j]].count(w2[j]) == 0) {
                    graph[w1[j]].insert(w2[j]);
                    inDegree[w2[j]]++;
                }
                break;
            }
        }
    }

    queue<char> q;
    for (auto& p : inDegree) {
        if (p.second == 0) q.push(p.first);
    }

    string order;
    while (!q.empty()) {
        char c = q.front(); q.pop();
        order += c;
        for (char nei : graph[c]) {
            inDegree[nei]--;
            if (inDegree[nei] == 0) q.push(nei);
        }
    }

    if ((int)order.size() != (int)inDegree.size()) return "";
    return order;
}

int main() {
    vector<string> words = {"wrt","wrf","er","ett","rftt"};
    cout << alienOrder(words) << endl;
    return 0;
}

Line Notes

unordered_map<char, unordered_set<char>> graph;Adjacency list for graph edges

unordered_map<char, int> inDegree;Map to track incoming edges count

if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen))Detect invalid prefix ordering

if (w1[j] != w2[j])Find first differing character to infer order

graph[w1[j]].insert(w2[j]);Add edge from w1[j] to w2[j]

inDegree[w2[j]]++;Increment in-degree of w2[j]

for (auto& p : inDegree)Initialize queue with zero in-degree characters

while (!q.empty())Process characters in topological order

if ((int)order.size() != (int)inDegree.size())Detect cycle by comparing processed count

var alienOrder = function(words) {
    const graph = new Map();
    const inDegree = new Map();

    for (const word of words) {
        for (const c of word) {
            if (!graph.has(c)) graph.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];
        const minLen = Math.min(w1.length, w2.length);
        if (w1.length > w2.length && w1.startsWith(w2)) return "";
        for (let j = 0; j < minLen; j++) {
            if (w1[j] !== w2[j]) {
                if (!graph.get(w1[j]).has(w2[j])) {
                    graph.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 order = [];
    while (queue.length > 0) {
        const c = queue.shift();
        order.push(c);
        for (const nei of graph.get(c)) {
            inDegree.set(nei, inDegree.get(nei) - 1);
            if (inDegree.get(nei) === 0) queue.push(nei);
        }
    }

    if (order.length !== inDegree.size) return "";
    return order.join("");
};

// Driver code
const words = ["wrt","wrf","er","ett","rftt"];
console.log(alienOrder(words));

Line Notes

const graph = new Map();Initialize adjacency list as a Map of Sets

const inDegree = new Map();Track incoming edges count per character

if (w1.length > w2.length && w1.startsWith(w2)) return "";Detect invalid prefix ordering

if (w1[j] !== w2[j])Find first differing character to infer order

graph.get(w1[j]).add(w2[j]);Add directed edge from w1[j] to w2[j]

inDegree.set(w2[j], inDegree.get(w2[j]) + 1);Increment in-degree of w2[j]

for (const [c, deg] of inDegree.entries())Initialize queue with zero in-degree characters

while (queue.length > 0)Process characters in topological order

if (order.length !== inDegree.size)Detect cycle by comparing processed count

⏱

Complexity

TimeO(C) where C is total characters in all words

SpaceO(U + E) where U is unique chars, E is edges

We compare adjacent words once, building edges only for first differing chars, then do a BFS topological sort over unique characters.

💡 For 100,000 words averaging 10 chars each, this means about 1 million operations, which is feasible but not optimal if implemented inefficiently.

Interview Verdict: Accepted

Though called brute force, this approach is actually the standard solution and accepted. It is the baseline to understand before exploring DFS-based topological sort.

🧠

DFS Postorder Topological Sort

💡 This approach uses DFS to perform a postorder traversal to generate a topological order, which is a classic method for topological sorting and helps detect cycles naturally.

Intuition

Build a graph from the inferred character order, then run DFS on each node, adding nodes to the order after visiting all descendants. If a cycle is detected during DFS, return empty string.

Algorithm

1. Build a graph and initialize visitation states for each character.
2. For each character, if unvisited, run DFS to visit all descendants.
3. During DFS, mark nodes as visiting; if a visiting node is encountered again, a cycle exists.
4. Add nodes to a stack or list after visiting descendants (postorder).
5. Reverse the collected order to get the correct character order.

💡 The key difficulty is understanding how DFS postorder naturally produces a valid topological order and how cycle detection is integrated.

</>

Code

from collections import defaultdict

def alienOrder(words):
    graph = defaultdict(set)
    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]:
                graph[w1[j]].add(w2[j])
                break

    visited = {}  # char: 0=unvisited, 1=visiting, 2=visited
    order = []

    def dfs(c):
        if c in visited:
            return visited[c] == 2
        visited[c] = 1
        for nei in graph[c]:
            if not dfs(nei):
                return False
        visited[c] = 2
        order.append(c)
        return True

    all_chars = set(''.join(words))
    for c in all_chars:
        if c not in visited:
            if not dfs(c):
                return ""

    return ''.join(order[::-1])

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

Line Notes

graph = defaultdict(set)Build adjacency list for character order

if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]Detect invalid prefix ordering

visited = {}Track visitation state for cycle detection

def dfs(c):DFS function returns False if cycle detected

visited[c] = 1Mark node as visiting to detect cycles

for nei in graph[c]:Visit all neighbors recursively

visited[c] = 2Mark node as fully visited after descendants

order.append(c)Add node postorder for topological sort

for c in all_chars:Run DFS on all characters to cover disconnected graph

import java.util.*;

public class AlienDictionaryDFS {
    Map<Character, Set<Character>> graph = new HashMap<>();
    Map<Character, Integer> visited = new HashMap<>(); // 0=unvisited,1=visiting,2=visited
    StringBuilder order = new StringBuilder();

    public String alienOrder(String[] words) {
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
            for (int j = 0; j < minLen; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    graph.computeIfAbsent(w1.charAt(j), k -> new HashSet<>()).add(w2.charAt(j));
                    break;
                }
            }
        }

        Set<Character> allChars = new HashSet<>();
        for (String w : words) {
            for (char c : w.toCharArray()) {
                allChars.add(c);
            }
        }

        for (char c : allChars) {
            if (!visited.containsKey(c)) {
                if (!dfs(c)) return "";
            }
        }

        return order.reverse().toString();
    }

    private boolean dfs(char c) {
        visited.put(c, 1);
        for (char nei : graph.getOrDefault(c, Collections.emptySet())) {
            if (!visited.containsKey(nei)) {
                if (!dfs(nei)) return false;
            } else if (visited.get(nei) == 1) {
                return false;
            }
        }
        visited.put(c, 2);
        order.append(c);
        return true;
    }

    public static void main(String[] args) {
        AlienDictionaryDFS sol = new AlienDictionaryDFS();
        String[] words = {"wrt","wrf","er","ett","rftt"};
        System.out.println(sol.alienOrder(words));
    }
}

Line Notes

Map<Character, Set<Character>> graph = new HashMap<>()Adjacency list for character graph

if (w1.length() > w2.length() && w1.startsWith(w2)) return "";Detect invalid prefix ordering

visited = new HashMap<>()Track visitation state for cycle detection

if (!visited.containsKey(c))Start DFS only on unvisited nodes

visited.put(c, 1)Mark node as visiting to detect cycles

for (char nei : graph.getOrDefault(c, Collections.emptySet()))Visit neighbors recursively

if (visited.get(nei) == 1)Cycle detected if neighbor is visiting

visited.put(c, 2)Mark node as visited after descendants

order.append(c)Add node postorder for topological order

return order.reverse().toString()Reverse postorder to get correct order

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

class Solution {
    unordered_map<char, unordered_set<char>> graph;
    unordered_map<char, int> visited; // 0=unvisited,1=visiting,2=visited
    string order;

    bool dfs(char c) {
        visited[c] = 1;
        for (char nei : graph[c]) {
            if (visited[nei] == 0) {
                if (!dfs(nei)) return false;
            } else if (visited[nei] == 1) {
                return false;
            }
        }
        visited[c] = 2;
        order.push_back(c);
        return true;
    }

public:
    string alienOrder(vector<string>& words) {
        for (int i = 0; i < (int)words.size() - 1; i++) {
            string& w1 = words[i], &w2 = words[i + 1];
            int minLen = min(w1.size(), w2.size());
            if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen))
                return "";
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    graph[w1[j]].insert(w2[j]);
                    break;
                }
            }
        }

        unordered_set<char> allChars;
        for (auto& w : words) {
            for (char c : w) allChars.insert(c);
        }

        for (char c : allChars) {
            if (visited[c] == 0) {
                if (!dfs(c)) return "";
            }
        }

        reverse(order.begin(), order.end());
        return order;
    }
};

int main() {
    vector<string> words = {"wrt","wrf","er","ett","rftt"};
    Solution sol;
    cout << sol.alienOrder(words) << endl;
    return 0;
}

Line Notes

unordered_map<char, unordered_set<char>> graph;Adjacency list for character graph

if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen))Detect invalid prefix ordering

unordered_map<char, int> visited;Track visitation state for cycle detection

visited[c] = 1;Mark node as visiting to detect cycles

for (char nei : graph[c])Visit neighbors recursively

if (visited[nei] == 1)Cycle detected if neighbor is visiting

visited[c] = 2;Mark node as visited after descendants

order.push_back(c);Add node postorder for topological order

reverse(order.begin(), order.end());Reverse postorder to get correct order

var alienOrder = function(words) {
    const graph = new Map();
    for (let i = 0; i < words.length - 1; i++) {
        const w1 = words[i], w2 = words[i + 1];
        const minLen = Math.min(w1.length, w2.length);
        if (w1.length > w2.length && w1.startsWith(w2)) return "";
        for (let j = 0; j < minLen; j++) {
            if (w1[j] !== w2[j]) {
                if (!graph.has(w1[j])) graph.set(w1[j], new Set());
                graph.get(w1[j]).add(w2[j]);
                break;
            }
        }
    }

    const visited = new Map(); // 0=unvisited,1=visiting,2=visited
    const order = [];

    function dfs(c) {
        if (visited.get(c) === 1) return false;
        if (visited.get(c) === 2) return true;
        visited.set(c, 1);
        for (const nei of (graph.get(c) || [])) {
            if (!dfs(nei)) return false;
        }
        visited.set(c, 2);
        order.push(c);
        return true;
    }

    const allChars = new Set(words.join(''));
    for (const c of allChars) {
        if (!visited.has(c)) {
            if (!dfs(c)) return "";
        }
    }

    return order.reverse().join("");
};

// Driver code
const words = ["wrt","wrf","er","ett","rftt"];
console.log(alienOrder(words));

Line Notes

const graph = new Map();Adjacency list for character graph

if (w1.length > w2.length && w1.startsWith(w2)) return "";Detect invalid prefix ordering

const visited = new Map();Track visitation state for cycle detection

if (visited.get(c) === 1) return false;Cycle detected if node is visiting

visited.set(c, 1);Mark node as visiting

for (const nei of (graph.get(c) || []))Visit neighbors recursively

visited.set(c, 2);Mark node as visited after descendants

order.push(c);Add node postorder for topological order

return order.reverse().join("");Reverse postorder to get correct order

⏱

Complexity

TimeO(C + U + E) where C is total chars, U unique chars, E edges

SpaceO(U + E) for graph and recursion stack

Build graph by comparing adjacent words, then DFS each node once. Cycle detection is integrated in DFS.

💡 For 1 million characters, DFS visits each node and edge once, making it efficient and scalable.

Interview Verdict: Accepted

This is the optimal and most common approach for this problem in interviews, demonstrating mastery of DFS and cycle detection.

🧠

Kahn's Algorithm (BFS) for Topological Sort

💡 This approach uses BFS and in-degree counting to perform topological sorting, which is intuitive and often easier to implement correctly than DFS.

Intuition

Build the graph and track in-degree of each character. Start with characters having zero in-degree and remove edges iteratively, adding new zero in-degree characters to the queue.

Algorithm

1. Build graph and compute in-degree for each character.
2. Initialize a queue with all characters having zero in-degree.
3. While queue not empty, remove character, append to order, and decrement in-degree of neighbors.
4. If cycle detected (not all characters processed), return empty string; else return order.

💡 The main challenge is correctly updating in-degree and detecting cycles by verifying all nodes are processed.

</>

Code

from collections import defaultdict, deque

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

    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]:
                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])
    order = []
    while queue:
        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):
        return ""
    return "".join(order)

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

Line Notes

graph = defaultdict(set)Build adjacency list for graph

in_degree = {c: 0 for word in words for c in word}Initialize in-degree for all characters

if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]Detect invalid prefix ordering

if w1[j] != w2[j]Find first differing character to infer order

graph[w1[j]].add(w2[j])Add edge from w1[j] to w2[j]

in_degree[w2[j]] += 1Increment in-degree of w2[j]

queue = deque([c for c in in_degree if in_degree[c] == 0])Start BFS with zero in-degree nodes

while queue:Process nodes in topological order

if len(order) != len(in_degree)Detect cycle if not all nodes processed

import java.util.*;

public class AlienDictionaryBFS {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();

        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.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];
            int minLen = Math.min(w1.length(), w2.length());
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    char c1 = w1.charAt(j), c2 = w2.charAt(j);
                    if (!graph.get(c1).contains(c2)) {
                        graph.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 order = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char nei : graph.get(c)) {
                inDegree.put(nei, inDegree.get(nei) - 1);
                if (inDegree.get(nei) == 0) queue.offer(nei);
            }
        }

        if (order.length() != inDegree.size()) return "";
        return order.toString();
    }

    public static void main(String[] args) {
        AlienDictionaryBFS sol = new AlienDictionaryBFS();
        String[] words = {"wrt","wrf","er","ett","rftt"};
        System.out.println(sol.alienOrder(words));
    }
}

Line Notes

Map<Character, Set<Character>> graph = new HashMap<>()Adjacency list for graph

Map<Character, Integer> inDegree = new HashMap<>()Track incoming edges count

if (w1.length() > w2.length() && w1.startsWith(w2))Detect invalid prefix ordering

if (w1.charAt(j) != w2.charAt(j))Find first differing character

graph.get(c1).add(c2)Add edge from c1 to c2

inDegree.put(c2, inDegree.get(c2) + 1)Increment in-degree of c2

for (char c : inDegree.keySet())Initialize queue with zero in-degree nodes

while (!queue.isEmpty())Process nodes in topological order

if (order.length() != inDegree.size())Detect cycle if not all nodes processed

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <string>
using namespace std;

string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    unordered_map<char, int> inDegree;

    for (auto& word : words) {
        for (char c : word) {
            graph[c];
            inDegree[c] = 0;
        }
    }

    for (int i = 0; i < (int)words.size() - 1; i++) {
        string& w1 = words[i], &w2 = words[i + 1];
        int minLen = min(w1.size(), w2.size());
        if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen))
            return "";
        for (int j = 0; j < minLen; j++) {
            if (w1[j] != w2[j]) {
                if (graph[w1[j]].count(w2[j]) == 0) {
                    graph[w1[j]].insert(w2[j]);
                    inDegree[w2[j]]++;
                }
                break;
            }
        }
    }

    queue<char> q;
    for (auto& p : inDegree) {
        if (p.second == 0) q.push(p.first);
    }

    string order;
    while (!q.empty()) {
        char c = q.front(); q.pop();
        order += c;
        for (char nei : graph[c]) {
            inDegree[nei]--;
            if (inDegree[nei] == 0) q.push(nei);
        }
    }

    if ((int)order.size() != (int)inDegree.size()) return "";
    return order;
}

int main() {
    vector<string> words = {"wrt","wrf","er","ett","rftt"};
    cout << alienOrder(words) << endl;
    return 0;
}

Line Notes

unordered_map<char, unordered_set<char>> graph;Adjacency list for graph

unordered_map<char, int> inDegree;Track incoming edges count

if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen))Detect invalid prefix ordering

if (w1[j] != w2[j])Find first differing character

graph[w1[j]].insert(w2[j]);Add edge from w1[j] to w2[j]

inDegree[w2[j]]++;Increment in-degree of w2[j]

for (auto& p : inDegree)Initialize queue with zero in-degree nodes

while (!q.empty())Process nodes in topological order

if ((int)order.size() != (int)inDegree.size())Detect cycle if not all nodes processed

var alienOrder = function(words) {
    const graph = new Map();
    const inDegree = new Map();

    for (const word of words) {
        for (const c of word) {
            if (!graph.has(c)) graph.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];
        const minLen = Math.min(w1.length, w2.length);
        if (w1.length > w2.length && w1.startsWith(w2)) return "";
        for (let j = 0; j < minLen; j++) {
            if (w1[j] !== w2[j]) {
                if (!graph.get(w1[j]).has(w2[j])) {
                    graph.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 order = [];
    while (queue.length > 0) {
        const c = queue.shift();
        order.push(c);
        for (const nei of graph.get(c)) {
            inDegree.set(nei, inDegree.get(nei) - 1);
            if (inDegree.get(nei) === 0) queue.push(nei);
        }
    }

    if (order.length !== inDegree.size) return "";
    return order.join("");
};

// Driver code
const words = ["wrt","wrf","er","ett","rftt"];
console.log(alienOrder(words));

Line Notes

const graph = new Map();Adjacency list for graph

const inDegree = new Map();Track incoming edges count

if (w1.length > w2.length && w1.startsWith(w2)) return "";Detect invalid prefix ordering

if (w1[j] !== w2[j])Find first differing character

graph.get(w1[j]).add(w2[j]);Add edge from w1[j] to w2[j]

inDegree.set(w2[j], inDegree.get(w2[j]) + 1);Increment in-degree of w2[j]

for (const [c, deg] of inDegree.entries())Initialize queue with zero in-degree nodes

while (queue.length > 0)Process nodes in topological order

if (order.length !== inDegree.size)Detect cycle if not all nodes processed

⏱

Complexity

TimeO(C + U + E) where C is total chars, U unique chars, E edges

SpaceO(U + E) for graph and queue

Build graph by comparing adjacent words, then BFS topological sort using in-degree counts.

💡 This approach is intuitive and efficient, suitable for large inputs.

Interview Verdict: Accepted

This BFS approach is an alternative to DFS and equally optimal, often preferred for clarity and cycle detection.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (DFS) or 3 (BFS) are optimal and preferred in interviews; Approach 1 is foundational but less efficient.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Compare Adjacent Words + BFS)	O(C + U + E)	O(U + E)	No	Yes	Mention as baseline, usually coded
2. DFS Postorder Topological Sort	O(C + U + E)	O(U + E + recursion stack)	Yes (deep recursion)	Yes	Optimal, preferred for demonstrating DFS skills
3. Kahn's Algorithm (BFS)	O(C + U + E)	O(U + E)	No	Yes	Optimal, preferred for clarity and cycle detection

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs and edge cases clearly in interviews.

How to Present

Clarify problem constraints and ask about invalid inputs.Explain brute force approach by comparing adjacent words and building graph edges.Discuss cycle detection and topological sorting necessity.Present DFS postorder topological sort with cycle detection.Optionally mention BFS Kahn's algorithm as an alternative.Write clean, tested code and walk through examples.Discuss edge cases and complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Discuss: 7min. Total ~30min

What the Interviewer Tests

Understanding of graph construction from strings, cycle detection, topological sorting, and ability to handle edge cases and large inputs.

Common Follow-ups

• What if input words contain characters not in the alphabet? → Handle by including all chars seen.
• How to detect invalid order or cycles? → Use visitation states in DFS or check processed count in BFS.
• Can multiple valid orders exist? → Yes, return any valid order.
• How to optimize for very large inputs? → Efficient graph building and early cycle detection.

💡 These follow-ups test robustness and deeper understanding of graph algorithms and problem constraints.

🔍

Pattern Recognition

When to Use

1) Given sorted list of strings in unknown alphabet, 2) Need to infer character order, 3) Order must satisfy constraints, 4) Detect cycles or invalid order

Signature Phrases

sorted lexicographically in alien languagederive order of charactersreturn empty string if invalid

NOT This Pattern When

Sorting strings by normal lex order or substring matching problems

Similar Problems

Course Schedule - also uses topological sort to detect order and cyclesSequence Reconstruction - reconstruct sequence from subsequences using graphMinimum Height Trees - uses graph traversal but different goal

Practice

1. Consider the following Python code implementing the optimal leaf trimming approach for Minimum Height Trees. Given n = 4 and edges = [[1,0],[1,2],[1,3]], what is the final returned list?

easy

A. [3]

B. [0, 2, 3]

C. [2]

D. [1]

Solution

1. Step 1: Initialize graph and degrees

   Nodes: 0,1,2,3; edges connect 1 to 0,2,3. Degrees: 0->1, 1->3, 2->1, 3->1. Leaves initially: [0,2,3].

2. Step 2: Trim leaves until ≤ 2 nodes remain

   Remove leaves [0,2,3], decrement neighbors' degrees. Node 1 degree reduces from 3 to 0, becomes leaf. Remaining nodes = 4 - 3 = 1. Loop ends. Return [1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only node 1 remains as centroid after trimming [OK]

Hint: Leaves trimmed until ≤2 nodes remain [OK]

Common Mistakes:

• Returning initial leaves
• Off-by-one in loop
• Not updating degrees correctly

2. You are given a list of sequences, each representing partial orderings of elements. Your task is to determine if there exists exactly one sequence that can be constructed which is consistent with all these partial orderings and matches a given original sequence. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Use brute force to generate all permutations of the original sequence and check which ones are supersequences of all given sequences.

B. Apply a greedy approach by always choosing the smallest available element not yet placed, hoping to build the unique sequence.

C. Use dynamic programming to count the number of ways to interleave the sequences and verify if only one matches the original.

D. Construct a directed graph from the sequences and perform a DFS postorder topological sort with cycle detection and uniqueness verification.

Solution

1. Step 1: Understand problem constraints

   The problem requires verifying if exactly one sequence matches all partial orderings, which is a classic unique topological order problem.

2. Step 2: Identify suitable algorithm

   Brute force is inefficient; greedy and DP approaches do not guarantee correctness or uniqueness checks. DFS postorder topological sort with cycle detection and uniqueness verification efficiently solves the problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DFS topological sort with uniqueness check is standard for unique sequence reconstruction [OK]

Hint: Unique topo order requires graph + DFS with uniqueness check [OK]

Common Mistakes:

• Assuming greedy or DP can guarantee uniqueness
• Trying brute force despite factorial complexity

3. What is the time complexity of the optimized topological sort approach for building the matrix with conditions, given n elements and m conditions?

medium

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

B. O(n * m) because each node is processed for all edges

C. O(m^2) due to repeated in-degree updates for each edge

D. O(n^2) because the adjacency list can be dense in worst case

Solution

1. Step 1: Identify operations in topological sort

   Each node is enqueued and dequeued once; each edge is visited once to decrement in-degree.

2. Step 2: Sum up total operations

   Total time is proportional to number of nodes plus number of edges: O(n + m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort complexity [OK]

Hint: Topological sort BFS is O(V+E) [OK]

Common Mistakes:

• Confusing with O(n*m) from nested loops
• Assuming dense graph implies O(n^2) always

4. The following code attempts to find eventual safe states using the reversed graph and Kahn's algorithm. Identify the line containing the subtle bug that causes incorrect results on some inputs.

from collections import deque

def eventualSafeNodes(graph):
    n = len(graph)
    reverse_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u in range(n):
        for v in graph[u]:
            reverse_graph[v].append(u)
        in_degree[u] = len(graph[u])  # Bug fixed here

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    safe = []

    while queue:
        node = queue.popleft()
        safe.append(node)
        for prev in reverse_graph[node]:
            in_degree[prev] -= 1
            if in_degree[prev] == 0:
                queue.append(prev)

    return sorted(safe)

medium

A. Line initializing queue with nodes having in_degree zero

B. Line appending u to reverse_graph[v]

C. Line decrementing in_degree[prev] inside the while loop

D. Line setting in_degree[v] = len(graph[u]) inside the outer loop

Solution

1. Step 1: Identify in-degree assignment error

   In-degree should be assigned per node u, but the original code assigned in_degree[v] inside inner loop, overwriting multiple times incorrectly.

2. Step 2: Correct assignment

   It should be in_degree[u] = len(graph[u]) after inner loop completes, not in_degree[v].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect in-degree causes wrong queue initialization and wrong safe nodes [OK]

Hint: In-degree must be assigned per node, not per neighbor [OK]

Common Mistakes:

• Confusing in-degree and out-degree assignment
• Assigning in-degree inside inner loop incorrectly
• Misusing loop variables for in-degree

5. Suppose the problem is modified so that nodes can be revisited multiple times (cycles allowed), but the path must still have no two adjacent nodes with the same character. Which approach correctly adapts the solution?

hard

A. Switch to DFS with cycle detection and memoization to handle revisits and character constraints

B. Use the same topological sort + DP approach, ignoring cycles since character constraints prevent infinite loops

C. Apply Bellman-Ford algorithm to detect negative cycles and compute longest paths

D. Use iterative DP on topological order but reset dp values when cycles are detected

Solution

1. Step 1: Understand impact of cycles

   Topological sort is invalid with cycles, so iterative DP on topo order cannot be applied.

2. Step 2: Choose correct approach

   DFS with cycle detection and memoization can explore paths safely, avoiding infinite recursion and respecting character constraints.

3. Step 3: Why other options fail

   Ignoring cycles or resetting dp is incorrect; Bellman-Ford is for shortest paths and not suited here.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DFS with cycle detection handles cycles and constraints correctly [OK]

Hint: Cycles break topo sort; use DFS with cycle detection [OK]

Common Mistakes:

• Trying to apply topological sort on cyclic graphs
• Ignoring cycle detection leading to infinite loops
• Misapplying shortest path algorithms