Alien Dictionary

Learn how to solve this Data Structures and Algorithms problem so you can ace your next interview.

Topological Sorting

Maps

Stacks

hard

Written by

Kenny Polyack

Software Engineer

Kenny is a software engineer and technical leader with four years of professional experience spanning Amazon, Wayfair, and U.S. Digital Response. He has taught courses on Data Structures and Algorithms at Galvanize, helping over 30 students land new software engineering roles across the industry, and has personally received offers from Google, Square, and TikTok.

Tom Wagner

Senior Software Engineer

Tom has four years of experience developing software professionally, including experience at both Amazon and Pinterest. He is experienced both as an interviewer, conducting interviews on behalf of the companies he's worked for, and interviewee, as he has landed software engineering offers from Google, Twitter, Stripe, Airtable and Doordash during previous job searches.

Interview Problems

About interviewing.io

interviewing.io is a mock interview practice platform. In our lifetime we’ve hosted close to 100K mock interviews, conducted primarily by senior engineers from FAANG.

We have the recordings from these mock interviews, as well as post-interview feedback and outcomes. We’ve curated information from these interviews and interviewers to bring you the best guidance on solving interview problems on the web!

Table of contents

  • Problem Description
  • Examples Inputs and Outputs
  • Example 1
  • Example 2
  • Example 3
  • Constraints
  • Problem Solution
  • Watch Someone Solve Alien Dictionary
  • Problem Approaches
  • 1. Topological Sort with Breadth-First Search
  • Alien Dictionary Python and JavaScript Solutions - Topological Sort with Breadth-First Search
  • Time / Space Complexity Analysis
  • 2. Depth-First Search
  • Alien Dictionary Python and JavaScript Solutions - Depth-First Search
  • Time / Space Complexity Analysis
  • Similar Questions

Problem Description

You are given a list of lexicographically sorted words from an alien language. This language, despite sharing a character set with ASCII, has a unique order. Return the alphabetical order of all the letters found in the list of words. There may be more than one possible answer.

Examples Inputs and Outputs

Example 1

Input: words = ["kaa","akcd","akca","cak","cad"]

Output: "kdac"

Example 2

Input: words = ["b","a"]

Output: "ba"

Example 3

Input: words = ["ab","a","b"]

Output: ""

Constraints

  • 0 <= words.length <= 100
  • 0 <= words[i].length <= 100
  • The character set for words[i] is ASCII

Problem Solution

Problem Approaches

Some graph problems look like graph problems: the problem domain is classically graph-related (networking, travel between cities, etc), the task is to explicitly build a graph, or you're given a graph data structure as an input. The crux of this problem, however, is to see a graph where there isn't an obvious graph.

And it really isn't obvious - a list of strings does not immediately scream graph. How can we approach a problem like this in an interview setting and discover the graph? First, start by carefully understanding what the problem offers us. The given words are lexicographically ordered, which implies that a relative relationship between some the characters exists. We are asked to find a possible order for the characters in the list of words, and since there could be more than one order, this alerts us that this could be a kind of pathfinding problem - the imagined path being a valid order of all the characters following their corresponding relationships in the list of words.

Graphs come in many forms, so let's think concretely about what our graph might look like in this case. A graph is simply a collection of nodes (vectors), but what makes it come to life are the connections (edges) between the vectors: each vector contains a reference to any other vectors it may be connected to in the graph. Importantly, each vector is not organized absolutely within the graph - unlike, say, an array, where each member is indexed globally - but connections can exist between any two vectors, indicating either a bi-directional relationship (like a friend) or a directional relationship (like a one-way street). Since our input is ordered, it makes sense to represent the characters using a directed graph. Rather than trying to decipher exactly where a given character falls in the global order, we can try to figure out what character it comes before or after based on the relative lexicographical order.

Before moving on, we should also clarify with out interviewer if the input will always be "valid" - or in other words, if it will always result in a valid output. There are a couple edges cases we might want to defend against if the input is not always friendly. First, the problem asks us to return an alphabetical order for all the characters included in the input. We can imagine a case where a character within our graph is unreachable - due to a cycle - so this would indicate a character whose alphabetical order remains inconclusive. Second, it seems possible that the input can contain words followed by their own prefix, like in the case of "ab" and "a". This, too, will be invalid, since in a valid alphabet, prefixes would have precedence.

Let's divide our work into three steps: 1) Derive relational character data from the input list; 2) Build a graph based on these relations; 3) Traverse the graph to solve the problem (we'll consider two different approaches for this step).

Step 1: Derive relationships between characters

Example: ["kaa","akcd","akca","cak","cad"]

What relationships between characters can we extract from the example above? We know for certain that the first letters of each word are in order. This doesn't necessarily mean their order is complete - there could be letters between them in the alphabet - but we do know their relative positions are fixed, that is to say, the first letter of the first word necessarily comes before the first letter of the second word. The same conclusion can be drawn for the third word and the fourth word (since the second and third words share the same starting letter, we'll skip them for now). Let's keep track of these relationships:

alien_dictionary_helper_image
alien_dictionary_helper_image

Notice that we don't necessarily know exactly how these two groups relate to one another, but to build a graph we don't need absolute relationships.

What else can we deduce? Well, lexicographic order doesn't stop at the first letter - if the first letters are the same, then order is determined by the second letters. If those are the same, then the third, and so forth, until we find the first two unequal characters. So we can also infer from the second and third words:

alien_dictionary_helper_image
alien_dictionary_helper_image

Is there anything else we can determine conclusively? Nope! The order is arbitrary beyond the first different characters between two adjacent words, since the position of any subsequent letters does not impact lexicographic order. Here's a recap of what we were able to deduce for certain:

Step 2: Build the graph

Now that we have these relations, how can we use this information to build a data structure that will allow us to detemine a possible path through each character? It may be tempting to try to build the final ordered list directly, but we quickly notice that determining global order isn't a trivial task (especially for large inputs). For instance, since "k" comes before both "a" and "d", its not immediately obvious which should come next.

A directed graph will allow us to represent both of these possibilities, since we can show how multiple characters will come after a given character. All we need to build the graph is a list of vectors and their respective edges (the connections to any other vectors). This can be accomplished with an adjacency list: we'll use a hash map to store each vector as a key, with the corresponding value being a list of any subsequent characters.

Here's a visual representation of our graph:

alien_dictionary_helper_image

Now that we have derived the relational data from the input list and represented it with our graph, we'll look at two approaches for the final task: finding a path that connects each character. One thing to keep in mind - as a constraint of the problem, we need to determine an order that includes all the characters. Therefore, if we cannot access a character within our graph - marked by the presence of a cycle - we'll return an empty string to signify an invalid input.

1. Topological Sort with Breadth-First Search

Let's introduce another concept to help solve this problem: topological sort. Often used for problems involving dependency chains, topological sort on a directed graph offers us two very useful outcomes: cycle detection (determining if there is no valid starting point to our alphabet or if at least one character is unreachable), and, if no cycle is detected, a possible path through each vector. The word "sort" is right there in the name - this algorithm attempts to traverse the graph in a sorted order using a modified breadth-first search. Let's unpack the method.

Practically speaking, where would one begin an ordered traversal? The beginning of course! We define the beginning as any vector with no incoming edges, or, in other words, a character that does not have any characters found to precede it. Let's create another data structure to keep track of the number of incoming connections for each vector, typically called in-degrees. While building the adjacency list above, we can use another hash map to count the number of times each character appears as an edge.

We can see that "k" is a possible starting point since there are no characters that must precede it in our alphabet. We'll implement a breadth-first approach to traverse the graph from all possible starting points. Let's use a queue to store characters that have no in-degrees, and hence have no characters that must precede it, and when vectors are pulled off the queue, we'll add them to our output list. In this case, we initialize the queue with "k" in it, as well as any other characters with zero in-degrees if there were any.

So, where to next? Well, potentially any of the vectors that "k" connects to are part of a valid path ("a" or "d"), but according to the topological sort algorithm, we can only visit vectors with zero in-degrees. Luckily, once "k" is visited, it is effectively removed from the search space, so we need to update our in_degree counts, since "a" and "d" lost an incoming connection.

We can imagine "k" was removed from the graph:

alien_dictionary_helper_image

With this update, we can now add "d" to the queue of vectors with zero in-degrees and continue this process until the queue is empty. And the convenience of the queue is we can store multiple vectors with zero in-degrees to be eventually processed.

This is the basic pattern of topological sort. Once the queue is empty, we check if the number of elements in our output list matches the number of vectors in our graph - if so, we have successfully traversed each vector (no cycle is detected), and we return this as a possible answer.

ALIEN DICTIONARY PYTHON AND JAVASCRIPT SOLUTIONS - TOPOLOGICAL SORT WITH BREADTH-FIRST SEARCH
TIME / SPACE COMPLEXITY ANALYSIS
  • Time Complexity: O(C), where C is the number of letters in all the words. In the worst case, building the adjacency list would require visiting every letter in every word.
  • Space Complexity: O(1), since the number of possible characters is limited to ASCII, this remains constant regardless of the input size. Alternatively, we can mention that the adjacency list will use O(V+E) memory, where V is the number of vectors in the graph - unique characters from the input - and E is the number of edges in the graph - the relations we deduced between characters.

2. Depth-First Search

As an alternative approach for traversing the graph in a sorted order, we can use depth-first search. This does require a modification to our graph though, since, as a recursive alogrithm, depth-first traversal typically returns when a node with zero outgoing connections is reached (or the outgoing connections that do exist have already been visited).

This means we would effectively be building the output in reverse: the algorithm will first search for "starting points" - in this case, vectors with no outgoing connections - then gradually make its way back down the call stack, tracking the path in our output array. We can reverse this path and return the appropriate order, or, build the graph initially with edges reversed in our adjacency list (the method below) and avoid needing to reverse the output. And since our depth-first search is recursive, we won't need a queue anymore, but we will use a global set to track already visited vectors.

ALIEN DICTIONARY PYTHON AND JAVASCRIPT SOLUTIONS - DEPTH-FIRST SEARCH
TIME / SPACE COMPLEXITY ANALYSIS
  • Time Complexity: O(C), where C is the number of letters in all the words. In the worst case, building the adjacency list would require visiting every letter in every word.
  • Space Complexity: O(1), since the number of possible characters is limited to ASCII, this remains constant regardless of the input size. Alternatively, we can mention that the adjacency list will use O(V+E) memory, where V is the number of vectors in the graph - unique characters from the input - and E is the number of edges in the graph - the relations we deduced between characters.

Reveal solution

Similar Questions

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is anonymous, and you don't have to until you find a job.

Computer Dude