Learn and practice the Cyclic Sort and Topological Sort patterns to solve coding interview problems.

Educative-77 in Python: Accelerate Your Coding Interview Prep

This module will focus on two advanced sorting algorithms, Cyclic Sort and Topological Sort. These are often used in coding interviews as a way to distinguish between average and outstanding candidates. Cyclic Sort may only be used if the input list meets certain criteria, and in those situations, it’s the most efficient sorting algorithm possible. Topological Sort utilizes graph-based algorithms to deal with partially ordered elements. This module teaches us to recognize whether either of these advanced sorting techniques is applicable, as well as how to use them to solve the given problem.

Advanced Sorting Techniques



**Constraints:**

- $1 \leq$ `words.length` $\leq 10^3$
- $1 \leq$ `words[i].length` $\leq 20$
- `order.length` $== 26$
- All the characters in `words[i]` and `order` are lowercase English letters.



# Solution

So far, you've probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

## Naive approach

The naive approach involves iterating over the order string and the list of words simultaneously without preprocessing. Starting from the first word in the list, we compare it with each subsequent word to verify whether the sequence follows the lexicographical order defined by the alien language. For each comparison, we go through both words character by character and determine the position of each character by scanning the order string. If we find a pair of characters that differ, we use their positions in the order string to decide whether the words are in the correct order. If the current character in the first word comes before the corresponding character in the second word, the order is correct, and we break out of the comparison early. However, if it comes after, we immediately return false as the list is not sorted. If all characters match but one word is longer than the other (e.g., “apple” vs. “app”), we also return false because the longer word should not precede its prefix. If we complete all comparisons without finding any violations, we return true, confirming that the list is sorted according to the alien dictionary.

Since this approach relies on repeated scanning of the order list for each character comparison and checks every word against others in nested iterations, its time complexity can grow significantly, potentially up to $O(n^3)$ in the worst case.




## 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]$:


Let's solve the Verifying an Alien Dictionary problem using the Topological Sort pattern.

Cyclic Sort

Topological Sort

Conclusion

Solution: Verifying an Alien Dictionary

Statement