Unpack the core of topological sort, focusing on ordering dependencies and resolving compilation sequences efficiently.

Coding

Determines a valid linear ordering of nodes in a directed acyclic graph that has dependencies on each other, crucial in tasks like scheduling or dependency resolution.

Topological Sort

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral



**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.

Solution: Verifying an Alien Dictionary

Statement▼

Solution: Verifying an Alien Dictionary

Statement▼