DSA sheet · Graphs · Topological sort (BFS) pattern

Alien Dictionary

This is the last topological sort problem in the sheet, and the trickiest one, because nobody gives you the graph. You only get a list of words, and you have to build the edges yourself by comparing them. The teacher's lessons: each pair of neighbouring words gives at most one rule "x comes before y", and only from the first letter where they differ. Those rules are directed edges. Kahn's algorithm (in-degree + queue) then prints the letters in order. She also lists the two ways the input can be invalid: a contradiction (a cycle) and the prefix trap ("abc" written before "ab").

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics you need for this page
• Part A · Build the letter graph, then BFS topological sort (Kahn)
• Part B · Revision page

Part 0 · Graph basics

Nodes and edges

A graph is a set of points called nodes joined by edges. On this page the nodes are letters, and an edge (b)→(a) will mean "b comes before a in the alien alphabet".

• Undirected edge (x)—(y): works both ways.
• Directed edge (x)→(y): one way only. "b before a" does not mean "a before b", so our edges are directed.
• Weighted edge: an edge with a number on it (a cost). Not needed here.

Storing a graph

n = 4
edges = [(1, 0), (3, 0), (0, 2), (1, 3)]
adj = [[] for _ in range(n)]
for x, y in edges:
    adj[x].append(y)             # directed: only x -> y
print(adj)                       # [[2], [0, 3], [], [0]]

Letters as node numbers

There are only 26 lowercase letters, so we can number them 0 … 25: ord(ch) - ord('a'). For 'c' that's 99 − 97 = 2. Then plain lists of size 26 can hold the adjacency list, the in-degrees and a "present" flag. The teacher mentions the other option too: a dictionary keyed by the letter itself. Both work; the index way is simple and fast.

print(ord('c') - ord('a'))       # 2
print(chr(2 + ord('a')))         # c

Visited and connected components

Searches mark nodes as visited so they don't process a node twice or loop forever. A graph can be in several separate pieces (connected components), so we start searches from every suitable node, not just one. Here some letters may have no rules at all; they are tiny components of one node, and they still belong in the answer.

BFS and DFS

Grid problems treat each cell as a node with 4 neighbours (up, down, left, right, with a bounds check). Not needed here.

In-degree and topological order

The in-degree of a node is the number of arrows coming into it. A topological order lists all the nodes so that every arrow points forward: for every x → y, x appears before y. That's exactly an alphabet: if b → a, then b comes before a.

Kahn's algorithm (BFS topological sort)

1. Count every node's in-degree.
2. Push the nodes with in-degree 0 into a queue (nothing must come before them).
3. Pop a node, append it to the order, and reduce each child's in-degree by 1 (as if we deleted the arrow). If a child reaches 0, push it.
4. If the order is shorter than the number of nodes, some nodes never reached 0. That only happens when there is a cycle: no valid order exists.

from collections import deque

def kahn(n, adj):
    indeg = [0] * n
    for x in range(n):
        for y in adj[x]:
            indeg[y] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        x = queue.popleft()
        order.append(x)
        for y in adj[x]:
            indeg[y] -= 1
            if indeg[y] == 0:
                queue.append(y)
    return order if len(order) == n else []   # [] means a cycle

print(kahn(4, [[2], [0, 3], [], [0]]))   # [1, 3, 0, 2]
print(kahn(2, [[1], [0]]))               # []

Bonus: topological order with DFS

DFS can also do it: after a node has finished all its children, put it on a list. Reversing that list gives a topological order. Cycles are caught with a "on the current path" mark (grey). The teacher uses BFS for this problem, so this is only for reference.

def dfs_topo(n, adj):
    state = [0] * n                 # 0 new, 1 on path, 2 done
    out = []
    def dfs(x):
        state[x] = 1
        for y in adj[x]:
            if state[y] == 1:
                return False        # back to the current path: cycle
            if state[y] == 0 and not dfs(y):
                return False
        state[x] = 2
        out.append(x)               # all children finished
        return True
    for i in range(n):
        if state[i] == 0 and not dfs(i):
            return []
    return out[::-1]

print(dfs_topo(4, [[2], [0, 3], [], [0]]))   # [1, 3, 0, 2]

Part A · Build the letter graph, then Kahn's algorithm

LeetCode 269 (premium) · also on GeeksforGeeks as "Alien Dictionary"

1The question in simple words

An alien language uses the same lowercase letters a–z, but in an unknown order. Maybe their alphabet starts with b, then d… We don't know.

You get a list of words words, and you are told it is sorted lexicographically by the alien order, meaning sorted the way a dictionary is sorted, but using the alien alphabet. Your job:

• Return a string with every distinct letter that appears in the words, in the alien order.
• If the words can't be sorted under any order (the input contradicts itself), return the empty string "".
• If several orders are possible, any one of them is accepted.

words = ["baa", "abcd", "abca", "cab", "cad"]
answer: "bdac"

The very first pair already tells us something: "baa" is written before "abcd". Their first letters differ (b vs a), so in this language b comes before a. Strange for us, normal for them.

2What the constraints tell us

• The total number of characters over all words is up to about 10⁶. The teacher counts this for the example: 3 + 4 + 4 + 3 + 3 = 17 characters. So we must read each character only a few times: O(total characters).
• But there are only 26 possible letters. However long the input is, the graph has at most 26 nodes and at most 26 × 25 edges. So the graph part is tiny, almost constant.
• Letters are lowercase a–z → we can use list indices 0 … 25 instead of a dictionary.

3Intuition: how a real dictionary is ordered

The teacher asks: how do you find "aeronautics" in an English dictionary? First you jump to the a section. Inside it you don't look at "az…"; you look at "ae…". Then "aer…", and so on. Words are ordered by the first letter; when the first letters are equal, by the second; and so on.

Turn that round. If two neighbouring words in a sorted dictionary first differ at position j, then the letter of the first word at j comes before the letter of the second word at j. That's one rule, and it's a directed edge in a graph of letters. Collect all the rules, and the alphabet is any order that respects every arrow, which is a topological order.

4Building the logic from the teacher's examples

Rule 1: only the FIRST different letter tells you anything

Compare "air" and "bean" in English. "air" comes first, and the first letters differ: a before b ✓. Can we also say i comes before e (the second letters)? No. In English, e actually comes before i. "air" is first only because of a vs b. After the first difference, the remaining letters say nothing. The teacher's way of saying it: inside the a-words we have aa…, ab…, ac…, and inside the b-words ba…, bb…, …, so knowing one a-word and one b-word tells you nothing about their second letters.

Each neighbouring pair gives one edge

Why compare only neighbours (word i with word i + 1)? Because the list is sorted, any rule from a non-neighbour pair follows from the neighbour rules in between. With 5 words there are 4 pairs:

The teacher pauses after the second pair: we know b → a and d → a, but nothing yet about b vs d. Both "b d a" and "d b a" fit so far. She waits for more information, and the last pair settles it: b → d. Putting it together: b, then d, then a, then c → "bdac".

The letter graph

   (b) ─────────→ (a) ───→ (c)
     ╲             ↑
      ╲            │
       ──→ (d) ────┘

   in-degree:  b = 0   d = 1   a = 2   c = 1

Why a directed graph? "b before a" is not the same as "a before b". The arrow points from the earlier letter to the later one.

b has in-degree 0: no letter must come before it, so it's the smallest. That's the first letter of the answer. This is why topological sort fits: "sorted order" + "who comes before whom" = a topological order, and Kahn's BFS lets us print the letters one by one.

Rule 2: a contradiction = a cycle → return ""

Add one more word at the end: […, "cad", "cbd"]. Compare "cad" and "cbd": c = c, then a vs b → edge a → b. But the first pair said b → a. One rule says b comes first, the other says a comes first. The teacher calls this a contradictory situation: no alphabet can satisfy both.

   (b) ───→ (a)
    ↑        │
    └────────┘      a cycle: b → a → b

In graph terms, a contradiction is a cycle. How do we notice it in Kahn's algorithm? Nodes on a cycle never reach in-degree 0, so they never enter the queue and never reach the answer. So: if the answer is shorter than the number of distinct letters, there was a cycle → return "". That's why we need to count the distinct letters.

Rule 3: the prefix trap ("abc" before "ab") → return ""

Compare "abc" and "ab". j = 0: a = a. j = 1: b = b. Now the shorter word has ended, and there was no mismatch. In every dictionary a word comes before any longer word that starts with it: "ab" must come before "abc". (The teacher's example: three a's must come before four a's.) So if the longer word is written first, the list can't be sorted under any alphabet → return "" right away.

Why the "present" list is needed

We keep in-degrees for all 26 letters, and they all start at 0. When we fill the queue, letters like f, g, h, which never appear in the words, also have in-degree 0. Without a check we would print them. So we keep present[c] = "this letter appears somewhere", and only push letters that are present and have in-degree 0. The same list helps count the distinct letters: we add 1 to the count only the first time a letter is seen (if it's already marked, skip, so repeats aren't counted).

Don't add the same edge twice

Different pairs can give the same rule again (e.g. "b vs a" found in two places). The teacher adds an edge only if it isn't already in the children list.

5Approach steps

1. Make graph (26 empty lists), indegree (26 zeros) and present (26 False).
2. Go through every letter of every word: mark it present and count it the first time it's seen → total distinct letters.
3. For each neighbouring pair (i, i + 1), with i from 0 to n − 2: find the first j where the letters differ, looking only up to the shorter length.
   • No mismatch and the first word is longer → return "" (the prefix trap).
   • Mismatch → add edge w1[j] → w2[j] (if new) and add 1 to the in-degree of w2[j].
4. Push every letter that is present and has in-degree 0.
5. Kahn's loop: pop, append the letter to the answer, reduce each child's in-degree, push it at 0.
6. If the answer has fewer than total letters → cycle → return "". Otherwise return the answer.

6Code (Python)

from collections import deque

class Solution:
    def alienOrder(self, words):
        graph = [[] for _ in range(26)]   # graph[x] = letters that come after x
        indegree = [0] * 26
        present = [False] * 26
        total = 0                         # number of distinct letters

        for word in words:
            for ch in word:
                c = ord(ch) - ord('a')
                if not present[c]:        # count each letter only once
                    present[c] = True
                    total += 1

        n = len(words)
        for i in range(n - 1):            # neighbouring pairs only
            first = words[i]
            second = words[i + 1]
            min_len = min(len(first), len(second))
            j = 0
            while j < min_len and first[j] == second[j]:
                j += 1
            if j == min_len:              # no mismatch found
                if len(first) > len(second):
                    return ""             # prefix trap: "abc" before "ab"
            else:
                u = ord(first[j]) - ord('a')
                v = ord(second[j]) - ord('a')
                if v not in graph[u]:     # skip a rule we already have
                    graph[u].append(v)
                    indegree[v] += 1

        queue = deque()
        for c in range(26):
            if present[c] and indegree[c] == 0:
                queue.append(c)

        result = []
        while queue:
            u = queue.popleft()
            result.append(chr(u + ord('a')))
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)

        if len(result) != total:          # some letters stuck on a cycle
            return ""
        return "".join(result)

On GeeksforGeeks the method is called findOrder(self, words); the body is the same.

7Code line by line

8Dry run

words = ["baa", "abcd", "abca", "cab", "cad"]. Distinct letters: b, a, c, d → total = 4. Edges from the pair table in step 4: b → a, d → a, a → c, b → d.

Fill the queue by scanning a … z: only b is present with in-degree 0 → queue = [b].

Length 4 = total 4 → return "bdac" ✓

  (b)✓ ───→ (a) ───→ (c)
     ╲       ↑
      → (d) ─┘
  a still waits for d

  (b)✓ ───→ (a) ───→ (c)
     ╲       ↑
      → (d)✓─┘
  a is now free

Dry run of the contradiction

["baa", "abcd", "abca", "cab", "cad", "cbd"] adds edge a → b. In-degrees: a 2, b 1, c 1, d 1. No present letter has in-degree 0, so the queue starts empty, the answer stays "" (length 0 ≠ 4) → return "".

Dry run of the prefix trap

["abc", "ab"]: min_len = 2, j goes 0 → 1 → 2 with no mismatch. j == min_len and 3 > 2 → return "" before any BFS.

9Complexity & remember

• Time O(C), where C = total characters (up to 10⁶). Marking letters reads each character once. Comparing pairs reads each word at most twice. The BFS works on at most 26 letters and their edges. The teacher stresses that the for loop inside the BFS doesn't run "26 times for each letter": over the whole BFS it runs once per edge in total (b has 2 children, d has 1, a has 1). So the BFS is O(26 + E), which is tiny next to 10⁶.
• Space O(1): graph, in-degree, present and the queue are all sized by the 26 letters, not by the input. In the example there are 17 characters but only 4 letters ever go into the queue. (v not in graph[u] scans at most 25 entries, also constant.)

The teacher's closing advice: the hard part is breaking the problem into rules and remembering the two failure conditions. Re-watch and revise them every few days, or as a beginner you'll forget them within a week.

Part B · Revision page

s = Solution()
print(s.alienOrder(["baa", "abcd", "abca", "cab", "cad"]))               # bdac
print(repr(s.alienOrder(["baa", "abcd", "abca", "cab", "cad", "cbd"])))  # ''
print(repr(s.alienOrder(["abc", "ab"])))                                 # ''
print(s.alienOrder(["ab", "abc"]))                                       # abc
print(s.alienOrder(["wrt", "wrf", "er", "ett", "rftt"]))                 # wertf
print(s.alienOrder(["z", "x"]))                                          # zx
print(repr(s.alienOrder(["z", "x", "z"])))                               # ''

Based on this video: Alien Dictionary | Topological Sort (BFS)