Problem
Submissions

Solution: Verifying an Alien Dictionary

Statement

Naive approach

The naive approach for this problem is to iterate over the order list and words simultaneously. Start from the first word, then compare the order with all other words present in the list.

The time complexity for the naive approach is O(n3)O(n^3), since we’re iterating the order list and the complete list two times in nested loops. The space complexity of this naive approach is constant because we didn’t use any extra memory.

Optimized approach using topological sort

We can solve this problem using the topological sort pattern. Topological sort is used to find a linear ordering of elements that depend on or prioritize each other. For example, if A depends on B or if B has priority over A, B is listed before A in topological order.

For this problem, we’re given the list of words and the order of the alphabet. Using the order of the alphabet, we must check if the list of words is sorted lexicographically.

We can check adjacent words to see if they are in the correct order. For each word, the word on its right should be lexicographically larger, and the one on its left should be lexicographically smaller.

One thing to notice here is that we don’t need to compare all the words. We can just compare each pair of adjacent words instead. If all the pairs of adjacent words are in order, we can safely assume that the integrity is intact. Conversely, if any pair of adjacent words isn’t in order, we can assume that our order is not correct.

Let’s review the illustration to better understand the intuition described above with the help of a sample list of three words, [w1,w2,w3][w1, w2, w3]:

Problem
Submissions

Solution: Verifying an Alien Dictionary

Statement

Naive approach

The naive approach for this problem is to iterate over the order list and words simultaneously. Start from the first word, then compare the order with all other words present in the list.

The time complexity for the naive approach is O(n3)O(n^3), since we’re iterating the order list and the complete list two times in nested loops. The space complexity of this naive approach is constant because we didn’t use any extra memory.

Optimized approach using topological sort

We can solve this problem using the topological sort pattern. Topological sort is used to find a linear ordering of elements that depend on or prioritize each other. For example, if A depends on B or if B has priority over A, B is listed before A in topological order.

For this problem, we’re given the list of words and the order of the alphabet. Using the order of the alphabet, we must check if the list of words is sorted lexicographically.

We can check adjacent words to see if they are in the correct order. For each word, the word on its right should be lexicographically larger, and the one on its left should be lexicographically smaller.

One thing to notice here is that we don’t need to compare all the words. We can just compare each pair of adjacent words instead. If all the pairs of adjacent words are in order, we can safely assume that the integrity is intact. Conversely, if any pair of adjacent words isn’t in order, we can assume that our order is not correct.

Let’s review the illustration to better understand the intuition described above with the help of a sample list of three words, [w1,w2,w3][w1, w2, w3]: