What happens if you not including all unique characters in the graph and output?

Missing characters in final order Fix: Initialize graph and in-degree with all unique characters from input

Interview Prepchallenge-problemshardFacebookAmazonGoogleBloomberg

Alien Dictionary

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Alien Dictionary

hardMIXEDFacebookAmazonGoogle

Imagine discovering a new alien language with words sorted in an unknown order. You want to deduce the alphabet order from a sorted dictionary of alien words.

💡 This problem involves inferring order relations from partial information, which is tricky because the order isn't explicitly given. Beginners often struggle because it requires building and reasoning about a graph and performing a topological sort, which is a non-trivial concept.

📋

Problem Statement

Given a list of words sorted lexicographically in an alien language, derive the order of characters in the alien alphabet. 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 words contain only lowercase English letters

💡

Example

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

Outputwertf

From 'wrt' and 'wrf', we know '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'.

Words with single character → order is that character
Prefix case: ['abc', 'ab'] → invalid order, return empty string
All words identical → order is all unique chars in any order
Words with no ordering info between some chars → multiple valid orders possible

⚠️

Common Mistakes

Not checking prefix invalid case where a longer word precedes its prefix

Returns incorrect order or fails to detect invalid input

✅ Add explicit check comparing prefixes and return empty string if invalid

Adding duplicate edges and incrementing in-degree multiple times

In-degree counts become incorrect, causing wrong topological order or false cycle detection

✅ Use sets to store edges and check before adding to avoid duplicates

Using DFS without proper cycle detection states leading to infinite recursion

Stack overflow or incorrect cycle detection

✅ Use three-state visitation (unvisited, visiting, visited) to detect cycles correctly

Not including all unique characters in the graph and output

Missing characters in final order

✅ Initialize graph and in-degree with all unique characters from input

Returning output without reversing DFS postorder

Incorrect character order

✅ Reverse the output list after DFS to get correct topological order

🧠

Brute Force (Pairwise Comparison and Cycle Detection via DFS)

💡 This approach exists to build intuition by explicitly comparing every adjacent word pair to infer character order and then checking for cycles by DFS. It is straightforward but inefficient for large inputs.

Intuition

Compare each pair of adjacent words to find the first differing character, which gives a direct ordering between two characters. Build a graph of these relations and detect cycles using DFS to confirm if a valid order exists.

Algorithm

Initialize a graph with all unique characters as nodes.
Compare each adjacent pair of words to find the first differing character and add a directed edge from the first to the second.
Perform DFS on the graph to detect cycles and to generate a topological order.
If a cycle is detected, return an empty string; otherwise, return the topological order.

💡 The challenge is to carefully build the graph and then use DFS to both detect cycles and produce the order, which can be confusing at first.

</>

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def alienOrder(words):
    graph = defaultdict(set)
    all_chars = set(''.join(words))

    # Build graph edges
    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]:
                graph[w1[j]].add(w2[j])
                break

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

    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
        output.append(c)
        return True

    for c in all_chars:
        if c not in visited:
            if not dfs(c):
                return ""

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

# 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

all_chars = set(''.join(words))Collect all unique characters to ensure all nodes are included

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

graph[w1[j]].add(w2[j])Add directed edge indicating w1[j] comes before w2[j]

visited = {}Track visitation state to detect cycles during DFS

def dfs(c):Recursive DFS function to detect cycles and build topological order

if c in visited: return visited[c] == 2If node is fully processed, no cycle here; if visiting, cycle detected

visited[c] = 1Mark node as visiting (in recursion stack)

for nei in graph[c]:Visit all neighbors to check for cycles

visited[c] = 2Mark node as fully visited (processed)

output.append(c)Add node to output after all descendants processed

for c in all_chars: if c not in visited:Start DFS from all nodes to cover disconnected graph

return ''.join(output[::-1])Reverse output to get correct topological order

import java.util.*;

public class AlienDictionary {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Set<Character> allChars = new HashSet<>();
        for (String w : words) {
            for (char c : w.toCharArray()) allChars.add(c);
        }

        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;
                }
            }
        }

        Map<Character, Integer> visited = new HashMap<>(); // 0=unvisited,1=visiting,2=visited
        StringBuilder output = new StringBuilder();

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

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

    private boolean dfs(char c, Map<Character, Set<Character>> graph, Map<Character, Integer> visited, StringBuilder output) {
        if (visited.containsKey(c)) {
            return visited.get(c) == 2;
        }
        visited.put(c, 1);
        for (char nei : graph.getOrDefault(c, Collections.emptySet())) {
            if (!dfs(nei, graph, visited, output)) return false;
        }
        visited.put(c, 2);
        output.append(c);
        return true;
    }

    // Driver
    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 store edges

Set<Character> allChars = new HashSet<>()Collect all unique characters

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

graph.computeIfAbsent(w1.charAt(j), k -> new HashSet<>()).add(w2.charAt(j))Add directed edge from w1[j] to w2[j]

Map<Character, Integer> visited = new HashMap<>()Track visitation state for cycle detection

if (visited.containsKey(c)) { return visited.get(c) == 2; }If node fully processed, no cycle; if visiting, cycle detected

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

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

visited.put(c, 2)Mark node as fully visited

output.append(c)Add node to output after processing neighbors

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

for (char c : allChars)Start DFS from all nodes to cover disconnected graph

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> graph;
        unordered_set<char> allChars;
        for (auto& w : words) {
            for (char c : w) allChars.insert(c);
        }

        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_map<char, int> visited; // 0=unvisited,1=visiting,2=visited
        string output;

        function<bool(char)> dfs = [&](char c) {
            if (visited.count(c)) return visited[c] == 2;
            visited[c] = 1;
            for (char nei : graph[c]) {
                if (!dfs(nei)) return false;
            }
            visited[c] = 2;
            output.push_back(c);
            return true;
        };

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

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

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

Line Notes

unordered_map<char, unordered_set<char>> graphAdjacency list for graph edges

unordered_set<char> allCharsCollect all unique characters

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

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

unordered_map<char, int> visitedTrack visitation state for cycle detection

if (visited.count(c)) return visited[c] == 2If node fully processed, no cycle; if visiting, cycle detected

visited[c] = 1Mark node as visiting

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

visited[c] = 2Mark node as fully visited

output.push_back(c)Add node to output after processing neighbors

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

for (char c : allChars)Start DFS from all nodes to cover disconnected graph

var alienOrder = function(words) {
    const graph = new Map();
    const allChars = new Set(words.join(''));

    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.slice(0, minLen) === w2.slice(0, minLen)) 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 output = [];

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

    for (const c of allChars) {
        if (!visited.has(c)) {
            if (!dfs(c)) return "";
        }
    }

    return output.reverse().join('');
};

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

Line Notes

const graph = new Map()Adjacency list to store edges

const allChars = new Set(words.join(''))Collect all unique characters

if (w1.length > w2.length && w1.slice(0, minLen) === w2.slice(0, minLen)) return ""Detect invalid prefix ordering

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

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

if (visited.has(c)) return visited.get(c) === 2If node fully visited, no cycle here; if visiting, cycle detected

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

if (graph.has(c)) { for (const nei of graph.get(c)) }Visit all neighbors

visited.set(c, 2)Mark node as fully visited

output.push(c)Add node to output after processing neighbors

return output.reverse().join('')Reverse output to get correct order

for (const c of allChars)Start DFS from all nodes to cover disconnected graph

⏱

Complexity

TimeO(C) where C is total characters in all words plus edges for graph construction and DFS

SpaceO(U + E) where U is number of unique chars and E is number of edges

We compare adjacent words once, building edges for differing chars. DFS visits each node and edge once.

💡 For 100,000 words with average length 10, this means roughly 1 million operations, which is borderline for brute force but still feasible with efficient implementation.

Interview Verdict: Accepted but not optimal for very large inputs

This approach is good to understand the problem and graph building but can be slow for huge inputs due to repeated DFS calls.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS Cycle Detection)	`O(C) where C is total characters plus edges`	`O(U + E)`	Yes (deep recursion possible)	Yes	Mention only - never code due to complexity and risk
2. Better (Kahn's Algorithm BFS)	`O(C)`	`O(U + E)`	No	Yes	Code this approach for clarity and efficiency
3. Optimal (Kahn's Algorithm with Edge Deduplication and Early Checks)	`O(C)`	`O(U + E)`	No	Yes	Preferred final solution, handles edge cases robustly

Practice

(1/5)

1. You are given a string of digits and a target integer. You need to insert binary operators (+, -, *) between the digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions?

easy

A. Backtracking with enumeration of all possible operator insertions and operand splits

B. Greedy algorithm that inserts operators based on local evaluation to reach the target quickly

C. Dynamic programming that stores intermediate results for sub-expressions without operator insertion

D. Divide and conquer by splitting the string into halves and solving independently

3. Consider the following Python function implementing the single pass stack-based solution for Largest Rectangle in Histogram. What is the value of max_area returned when the input is [2, 4, 2]?

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Restore original list
    return max_area

easy

A. 2

B. 4

C. 6

D. 8

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem requirements

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Insert 1

Step 2: Insert 5

Step 3: Insert 3

Step 4: Find median

Final Answer:

Quick Check:

Solution

Step 1: Trace iterations with input [2,4,2]

Step 2: Return max_area

Final Answer:

Quick Check:

Solution

Step 1: Identify that left and right gains must ignore negative sums by using max(helper(...), 0).

Step 2: Notice that line assigning left = helper(node.left) lacks max(..., 0), causing negative gains to propagate.

Final Answer:

Quick Check:

Solution

Step 1: Identify divide and conquer structure

Step 2: Analyze merge cost per level

Final Answer:

Quick Check:

Ready to prove it?