March 24
Alien Dictionary
How to extract letter constraints from sorted words and turn them into a topological sort.
Graphs Advanced 30 min TypeScript
Given an array of words words sorted according to the alphabetical order of an alien language, return a string with one valid order of the letters.
Rules:
- if the input is invalid, return
"" - if more than one valid order exists, in the SeniorPath playground return the lexicographically smallest valid one to keep comparison deterministic
Example:
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
What to notice before coding
- Edges come from the first difference between two neighboring words.
- If a longer word appears before its own prefix, the input is invalid.
- Letters with no edges still need to appear in the answer.
Common mistakes
- continuing to compare characters after the first difference
- forgetting the invalid prefix case like `["abc", "ab"]`
Step 1 - Understand where the information comes from
The problem does not directly give you letter pairs.
It gives you:
- words that are already sorted
So you need to extract constraints from that ordering.
Step 2 - See which comparison really matters
Between two neighboring words, the ordering only reveals one thing:
- the first character where they differ
Example:
"wrt""wrf"
The first difference is t vs f.
So we know:
tcomes beforef
After that, the rest does not matter for this pair.
Step 3 - Handle the invalid case early
If you see:
"abc""ab"
that is impossible.
A longer word cannot come before its own prefix in lexicographic order.
Step 4 - Turn constraints into a graph
Once the edges are extracted, the problem becomes:
- find a linear order that respects all dependencies
That is topological sort.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function alienOrder(words: string[]): string {
// your solution here
return ""
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(C + V log V + E)
Space: O(V + E)
Solution 1 - Graph plus DFS with states
Good baseline because it makes both parts visible: building constraints and detecting cycles.
export function alienOrder(words: string[]): string {
const graph = new Map<string, Set<string>>()
for (const word of words) {
for (const char of word) {
if (!graph.has(char)) {
graph.set(char, new Set())
}
}
}
for (let index = 0; index < words.length - 1; index += 1) {
const first = words[index]
const second = words[index + 1]
if (first.length > second.length && first.startsWith(second)) {
return ""
}
const limit = Math.min(first.length, second.length)
for (let charIndex = 0; charIndex < limit; charIndex += 1) {
const from = first[charIndex]
const to = second[charIndex]
if (from !== to) {
graph.get(from)!.add(to)
break
}
}
}
const state = new Map<string, number>()
const order: string[] = []
function dfs(char: string): boolean {
if (state.get(char) === 1) {
return false
}
if (state.get(char) === 2) {
return true
}
state.set(char, 1)
for (const neighbor of graph.get(char)!) {
if (!dfs(neighbor)) {
return false
}
}
state.set(char, 2)
order.push(char)
return true
}
for (const char of graph.keys()) {
if (!dfs(char)) {
return ""
}
}
return order.reverse().join("")
}It works.
But for the playground we still want deterministic output when multiple letters are available at the same time.
Solution 2 - Kahn with indegree and a sorted queue
Now the order comes out in a controlled way.
export function alienOrder(words: string[]): string {
const graph = new Map<string, Set<string>>()
const indegree = new Map<string, number>()
for (const word of words) {
for (const char of word) {
if (!graph.has(char)) {
graph.set(char, new Set())
indegree.set(char, 0)
}
}
}
for (let index = 0; index < words.length - 1; index += 1) {
const first = words[index]
const second = words[index + 1]
if (first.length > second.length && first.startsWith(second)) {
return ""
}
const limit = Math.min(first.length, second.length)
for (let charIndex = 0; charIndex < limit; charIndex += 1) {
const from = first[charIndex]
const to = second[charIndex]
if (from !== to) {
if (!graph.get(from)!.has(to)) {
graph.get(from)!.add(to)
indegree.set(to, indegree.get(to)! + 1)
}
break
}
}
}
const available = [...graph.keys()].filter((char) => indegree.get(char) === 0).sort()
const order: string[] = []
while (available.length > 0) {
const char = available.shift()!
order.push(char)
for (const neighbor of [...graph.get(char)!].sort()) {
indegree.set(neighbor, indegree.get(neighbor)! - 1)
if (indegree.get(neighbor) === 0) {
available.push(neighbor)
}
}
available.sort()
}
return order.length === graph.size ? order.join("") : ""
}The strong insight here is that alien ordering is not guessed. It is derived from constraints and validated by the absence of cycles.
What to say in the interview
A strong short explanation would be:
I compare neighboring words and only use the first difference, because that is what creates a real ordering constraint between letters. Then I build a directed graph and solve it with topological sort. I also handle the invalid prefix case early, like
abcbeforeab, because that already makes the input impossible.
That shows that you:
- knew how to extract constraints from the input
- translated the problem into the right model
- covered both cycle handling and invalid prefix handling
When this pattern shows up again
This pattern comes back when you need to:
- deduce order from partial comparisons
- turn rules into directed edges
- use topological sort to find a valid ordering
- realize that “partial order” is not the same thing as “guessed order”
The point is not memorizing
Alien Dictionary.
The point is learning how to build the right graph from the right clues.