Blind 75 Visualized

#49 · Advanced Graphs

Alien Dictionary

You receive a list of words from an alien language, sorted lexicographically by that language's own alphabet. Return a string of its letters in a valid order, or an empty string if the ordering is inconsistent.

HardLeetCode
  • Current
  • On path / queued
  • Done
  • Cycle / blocked
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Directed graph of letter constraints

Each distinct letter is a node. Comparing two neighbouring words, the first position where they differ gives one rule: the letter in the earlier word comes before the letter in the later word. Any valid alphabet is a topological order of this graph.

Memory layout

An adjacency structure per letter: a hash set of successors, or for a lowercase alphabet a 26-bit mask per letter.

OperationCost
buildO(total characters)
orderO(V + E), V ≤ 26

Topological sort (Kahn or DFS)

Kahn: keep a queue of letters with no unplaced predecessor, place one, and lower the in-degree of its successors. DFS: visit successors first and append a letter when it finishes; reversing the finish list gives a valid order. Either also detects a cycle.

Memory layout

In-degree counters and a queue, or a 3-state array and a recursion stack.

OperationCost
topological orderO(V + E)

Why it fits

  • Sorted words contain only partial information about the alphabet: just "x before y" facts. A directed graph is the natural container for such facts.
  • A valid alphabet satisfies every fact at once, which is exactly what a topological order is; if the facts contradict each other there is a cycle and no order exists.
  • Only the first differing letter of two neighbouring words says anything. Later letters are unconstrained, and non-adjacent words add nothing new (their rules follow by chaining).

Why alternatives degrade

Sorting the letters somehow:
Without an order to sort by there is nothing to compare; the order is exactly what has to be discovered.
Comparing letters only in the first column:
Words sharing a first letter can still give rules in later columns, such as "ab…" before "ac…".
Ignoring the prefix rule:
A word like "abc" cannot come before "ab"; skipping that check accepts impossible input.

Four approaches, from naive to production

1 · beginner

Every pair of words, peel letters one by one

time O(n² · L + V³)space O(V + E)

Compare every pair of words and record the rule from the first differing letter. Then repeatedly look for a letter that no other remaining letter must precede, append it to the answer and remove it. If none exists, the rules have a cycle.

string alienOrder(vector<string>& words) {
    map<char, set<char>> adj;
    for (auto& w : words) for (char ch : w) if (!adj.count(ch)) adj[ch] = {};
    for (size_t i = 0; i < words.size(); i++) {
        for (size_t j = i + 1; j < words.size(); j++) {
            string a = words[i], b = words[j];
            size_t k = 0;
            while (k < a.size() && k < b.size() && a[k] == b[k]) k++;
            if (k < a.size() && k < b.size()) adj[a[k]].insert(b[k]);
            else if (a.size() > b.size()) return "";
        }
    }
    set<char> remaining; for (auto& kv : adj) remaining.insert(kv.first);
    string result;
    while (!remaining.empty()) {
        char pick = 0; bool found = false;
        for (char ch : remaining) {
            bool blocked = false;
            for (char other : remaining) if (adj[other].count(ch)) blocked = true;
            if (!blocked) {
                pick = ch; found = true;
                break;
            }
        }
        if (!found) return "";
        result += pick;
        remaining.erase(pick);
    }
    return result;
}

Flaws & bottlenecks

  • Comparing all pairs is quadratic in the number of words, though only neighbouring pairs matter.
  • It creates redundant rules (b → c here follows from b → a → c).
  • The selection loop rescans all remaining letters for every pick.

Interviewer cross-questions

Why are non-adjacent pairs unnecessary?

Say: The list is already sorted. If word1 < word2 < word3, the rule between word1 and word3 is implied by the chain of rules from the two neighbouring comparisons.

How is a cycle detected here?

Say: If every remaining letter is blocked by another remaining letter, no letter can go next, so the constraints loop back on themselves: return an empty string.

What is the cost of the selection loop?

Say: Each round checks each candidate against all remaining letters: O(V²) per round and O(V³) in total. V is at most 26, so it is cheap here, but it does not scale.

2 · intermediate

Neighbouring words + Kahn's algorithm

time O(total characters + V + E)space O(V + E)

Only compare neighbouring words. Store each rule once and count in-degrees. Queue the letters with in-degree 0; pop one, append it, decrement its successors and queue those that reach 0. If fewer letters are placed than exist, there is a cycle.

string alienOrder(vector<string>& words) {
    map<char, set<char>> adj;
    map<char, int> indegree;
    for (auto& w : words) {
        for (char ch : w) {
            if (!adj.count(ch)) {
                adj[ch] = {};
                indegree[ch] = 0;
            }
        }
    }
    for (size_t i = 0; i + 1 < words.size(); i++) {
        string a = words[i], b = words[i + 1];
        if (a.size() > b.size() && a.compare(0, b.size(), b) == 0) return "";
        for (size_t k = 0; k < min(a.size(), b.size()); k++) {
            if (a[k] != b[k]) {
                if (!adj[a[k]].count(b[k])) {
                    adj[a[k]].insert(b[k]);
                    indegree[b[k]]++;
                }
                break;
            }
        }
    }
    vector<char> queue;
    for (auto& [ch, d] : indegree) if (d == 0) queue.push_back(ch);
    string result;
    size_t head = 0;
    while (head < queue.size()) {
        char ch = queue[head++];
        result += ch;
        for (char next : adj[ch]) {
            indegree[next]--;
            if (indegree[next] == 0) queue.push_back(next);
        }
    }
    return result.size() == adj.size() ? result : "";
}

Flaws & bottlenecks

  • The in-degree must not be incremented twice for a repeated rule; that is why the set is checked first.
  • Easy to forget the "longer word before its own prefix" check, which no graph can reveal.
  • Letters that appear in no rule must still be in the answer, so they are added when words are scanned.

Interviewer cross-questions

Why is a repeated rule a problem?

Say: If two word pairs both say x before y, adding the rule twice would count y's in-degree twice, but x only decrements it once. y would never reach 0 and a valid input would look cyclic.

Is the answer unique?

Say: No. When two letters have no rule between them either order is valid; any topological order is accepted. Kahn returns one of them depending on queue order.

How does Kahn detect a cycle?

Say: Letters on a cycle always have an unplaced predecessor, so their in-degree never reaches 0. The final answer then has fewer letters than exist.

3 · advanced

Neighbouring words + DFS finish order

time O(total characters + V + E)space O(V + E)

Build the same graph, then depth-first search with three states per letter (new, visiting, done). Visit all successors first, then append the letter; the reversed finish list is a valid order. Reaching a "visiting" letter means a cycle.

string alienOrder(vector<string>& words) {
    map<char, set<char>> adj;
    for (auto& w : words) for (char ch : w) if (!adj.count(ch)) adj[ch] = {};
    for (size_t i = 0; i + 1 < words.size(); i++) {
        string a = words[i], b = words[i + 1];
        if (a.size() > b.size() && a.compare(0, b.size(), b) == 0) return "";
        for (size_t k = 0; k < min(a.size(), b.size()); k++) {
            if (a[k] != b[k]) {
                adj[a[k]].insert(b[k]);
                break;
            }
        }
    }
    map<char, int> state;
    string out;
    function<bool(char)> visit = [&](char ch) -> bool {
        int s = state[ch];
        if (s == 1) return false;
        if (s == 2) return true;
        state[ch] = 1;
        for (char next : adj[ch]) {
            if (!visit(next)) return false;
        }
        state[ch] = 2;
        out += ch;
        return true;
    };
    for (auto& kv : adj) {
        if (!visit(kv.first)) return "";
    }
    return string(out.rbegin(), out.rend());
}

Flaws & bottlenecks

  • The DFS must distinguish "visiting" from "done"; a plain visited set cannot tell a back edge from a harmless revisit.
  • Recursion depth is at most the number of letters (26), so it is safe, but the code is longer than Kahn for the same job.
  • The result depends on the iteration order of the letters; it is valid but not canonical.

Interviewer cross-questions

Why reverse the finish list?

Say: A letter finishes only after everything that must come after it has finished. So letters finish in reverse topological order, and reversing gives a valid alphabet.

Why three states instead of two?

Say: A letter that is "done" can be reached again harmlessly. A letter that is "visiting" is on the current path, so reaching it again is a cycle. Two states cannot separate the cases.

Kahn or DFS?

Say: Both are linear. Kahn is iterative and reports the order naturally; DFS is compact and also finds the cycle path. Pick the one you can write without bugs under pressure.

4 · expert

Letters as bits: masks, counters, Kahn

time O(total characters + 26²)space O(1) beyond the input (constant 26-entry tables)

Map letters to 0…25. Store each letter's successors as one integer bitmask (setting a bit twice is free), keep an in-degree array, find the first differing position of each neighbouring pair with a plain index loop, and run Kahn's algorithm over the 26 slots.

string alienOrder(vector<string>& words) {
    vector<bool> present(26, false);
    for (auto& w : words) for (char ch : w) present[ch - 'a'] = true;
    int out[26] = {0};
    int indegree[26] = {0};
    for (size_t i = 0; i + 1 < words.size(); i++) {
        string a = words[i], b = words[i + 1];
        size_t len = min(a.size(), b.size());
        size_t k = 0;
        while (k < len && a[k] == b[k]) k++;
        if (k == len) {
            if (a.size() > b.size()) return "";
            continue;
        }
        int x = a[k] - 'a', y = b[k] - 'a';
        if (!(out[x] & (1 << y))) {
            out[x] |= 1 << y;
            indegree[y]++;
        }
    }
    vector<int> queue;
    int total = 0;
    for (int c = 0; c < 26; c++) {
        if (!present[c]) continue;
        total++;
        if (indegree[c] == 0) queue.push_back(c);
    }
    string result;
    for (size_t head = 0; head < queue.size(); head++) {
        int x = queue[head];
        result += char('a' + x);
        for (int y = 0; y < 26; y++) {
            if ((out[x] & (1 << y)) && --indegree[y] == 0) queue.push_back(y);
        }
    }
    return (int)result.size() == total ? result : "";
}

Flaws & bottlenecks

  • Only works for a fixed small alphabet; a large or Unicode alphabet needs a hash map.
  • The bit tricks are less readable than sets.
  • It trusts the input to be lowercase letters; any other character indexes outside the arrays.

Interviewer cross-questions

Why a bitmask for the edges?

Say: A bit can be set many times with the same effect, so repeated rules are deduplicated for free, and testing or setting a rule is one machine instruction with no allocation.

What is the complexity of the topological step?

Say: The alphabet is at most 26 letters, so scanning 26 bits per placed letter is O(26²), a constant. The real cost is reading the words, linear in their total length.

How would you generalise this?

Say: Map arbitrary symbols to integers with a dictionary, and replace the mask by a set (or a bitset sized to the alphabet). The algorithm is unchanged.

Synchronized code walkthrough

Showing: Every pair of words, peel letters one by one — shares the player above; click any step to jump.

string alienOrder(vector<string>& words) {
    map<char, set<char>> adj;
    for (auto& w : words) for (char ch : w) if (!adj.count(ch)) adj[ch] = {};
    for (size_t i = 0; i < words.size(); i++) {
        for (size_t j = i + 1; j < words.size(); j++) {
            string a = words[i], b = words[j];
            size_t k = 0;
            while (k < a.size() && k < b.size() && a[k] == b[k]) k++;
            if (k < a.size() && k < b.size()) adj[a[k]].insert(b[k]);
            else if (a.size() > b.size()) return "";
        }
    }
    set<char> remaining; for (auto& kv : adj) remaining.insert(kv.first);
    string result;
    while (!remaining.empty()) {
        char pick = 0; bool found = false;
        for (char ch : remaining) {
            bool blocked = false;
            for (char other : remaining) if (adj[other].count(ch)) blocked = true;
            if (!blocked) {
                pick = ch; found = true;
                break;
            }
        }
        if (!found) return "";
        result += pick;
        remaining.erase(pick);
    }
    return result;
}