# Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website):

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of characters in the alien language.

Explanation: We're given a sorted dictionary having N words. Here a dictionary is an ordered list. A word is a sequence of allowed characters. There are 'K' allowed characters. These characters are first K alphabets of roman script. For example, K=5 implies that the allowed characters are {a, b, c, d, e}. But the ordering of the allowed characters is different in the alien language from standard roman script. For example, in the alien language the order of characters could be [b, d, e, a, c]. The words in the given dictionary are sorted lexicographically. Using the dictionary, we've to figure out the ordering of characters in the alien language.

Example test case: N = 5, K = 4, dict = ["baa","abcd","abca","cab","cad"]

Solution: {b, d, a, c}

Now the solution requires building a DAG. We iterate over the dictionary and compare every word to its next word to get information about the ordering of alphabets in the alien dictionary, i.e., pair-wise comparisons. In an optimal approach, (N-1) comparisons will be required to create the DAG (N being number of words in the dictionary). Every time we compare 2 word, we can infer something about the ordering of alphabets. This information is used to build the order of alphabets in the alien dictionary.

My first intuition was that every string in the dictionary can be compared to every string succeeding it thus totalling comparisons in order of N^2, i.e. [(n-1)+(n-2)+...+2+1] comparisons. But it turns out that N^2 comparisons aren't required. If we use only (N-1) comparisons as mentioned in previous paragraph, the information is sufficient to deduce the order of alphabets. How can I prove that the extra comparisons made in the N^2 approach will always be redundant giving no useful information?

• Please edit your post to make it self-contained by providing a specification of the problem, so people don't need to click on external links to understand what you are asking and so the question continues to make sense even if the link stops working. Why do you think it requires n^2 comparisons? Please explain what you mean by "the (n-1) comparison approach" and "the (n^2) comparison"/"the (n^2) approach".
– D.W.
Nov 15 at 19:59
• @D.W. I've edited my post. Let me know if it is okay now? Nov 16 at 1:37
• I don't understand what "k starting alphabets of standard dictionary" means. I don't understand the algorithm -- I'm not sure what "its next string" or "ordering of alphabets" means. I would expect that the alphabet is the set of allowable characters, e.g., {a,b,c,d}, and a word is a sequence of characters, and a dictionary is a set of words. Why do you believe that using only N-1 comparisons is sufficient? Which pairs of strings are you comparing?
– D.W.
Nov 16 at 3:12
• Suggestions: "k starting alphabets of standard dictionary" should perhaps be "K letters in the alien alphabet". The "dict = {...}" notation may be misleading. Edit to clarify that this is an ordered list, not a set, by writing $[w_1,w_2,\ldots,w_N]$.
– Kai
Nov 16 at 13:41
• @Kai I've edited the problem statement as you told. Thanks. Nov 20 at 5:32

Each pair of adjacent words $$w_i,w_{i+1}$$ in the dictionary list $$[w_1,\ldots,w_N]$$ generates at most one edge in the DAG. Why "at most"? (a) because that edge may be present already and (b) because $$w_i$$ could be a prefix of $$w_{i+1}$$. The suggested $$N-1$$ comparisons suffice because nothing new can be learned from studying $$w_i,w_{i+\ell}$$ for $$\ell > 1$$ that was not learned already by iterating through the $$N-1$$ adjacent pairs.
Let's prove that last claim. Roughly, this works as follows. Let $$\Sigma$$ be the alien alphabet. Suppose $$m,n,o$$ are minimal such that $$m and comparing $$w_m$$ with $$w_o$$ adds the edge $$(\alpha,\beta)$$ to the DAG $$(\Sigma,E)$$ we obtained by comparing the $$N-1$$ pairs $$(w_i,w_{i+1})$$ for $$1\leq i < N$$ and then forming the transitive closure.
For easier access to the letters of the three relevant words, set $$x_1\ldots x_{k_m} = w_m$$, $$y_1\ldots y_{k_n} = w_n$$, and $$z_1\ldots z_{k_o} = w_o$$. We know there exists $$j$$ such that $$\alpha = x_j \neq z_j = \beta$$ and, for all $$1\leq k we have $$x_k = z_k$$. (Otherwise we would not add $$(\alpha,\beta)$$.) We also know that $$x_k = y_k = z_k$$ for all $$1\leq k and that $$x_j\leq y_j\leq z_j$$ according to $$E$$. One of those "$$\leq$$" is strict, i.e., already in $$E$$. Either way, since we formed the transitive closure, $$(x_j,z_j)$$ is already in $$E$$ (or this is not the minimal example of $$m,n,o$$).
• In your point (b), did you mean to write that $w_i$ could be a prefix of $w_{i+1}$? Because if $w_i$ is a prefix of $w_{i-1}$, an example order in the dictionary would be $[\ldots, ab, a, \ldots]$ but 'ab' coming before 'a' is incorrect lexicographically. Nov 20 at 5:41
• You wrote that nothing new can be learned from studying $w_i,w_{i+\ell}$ for $\ell > 1$ that was not learned already by iterating through the $N-1$ adjacent pairs. How can I be sure of this? Can you prove it? Nov 20 at 5:44