The O(n) Club: Alien Dictionary: Sorting Out Topo-Sorted Antics

The O(n) Club: Alien Dictionary – Sorting Out Topo-Sorted Antics

⚡ TL;DR

The aliens dumped a list of words in your inbox and expect you to decode their alphabet—because, obviously, Google Translate hasn’t reached Alpha Centauri yet. The trick? Compare adjacent words, spot where they first differ, build a directed graph between letters, and topologically sort your way to peace in the galaxy. Cycles or weird prefixes? Abort mission.

// Attempting brute force? Here's what not to do:
public String alienOrder(String[] words) {
    int[] order = new int[26];
    // No, this won't cut it—topo sort is a must!
    return "";
}

🧠 How Devs Usually Mess This Up

If you’ve ever thought “I’ll just read off the letters in order and call it a day,” congratulations—you’ve made every space linguist facepalm. Here are the greatest hits:

• Treating the word order as a direct code: Only the first different letter between two neighbors tells you anything. Sorry, you can’t just list unique letters and take the afternoon off.
• Missing indirect constraints: It’s not a one-hop kind of galaxy. If ‘r’ comes before ‘s’ and ‘s’ before ‘t’, you need to string those together (because cause and effect is real, even for letters).
• Neglecting cycles: If your graph goes in circles, that’s not just dramatic irony—it’s an impossible order. Return an empty string and try not to cry.
• Ignoring prefix problems: Having “abc” before “ab” is the alphabetic equivalent of traffic driving backwards. Just don’t.

🔍 What’s Actually Going On

Imagine you’re a detective and every word is a cryptic ransom note. You’re not interested in the whole message—just looking for that first “aha!” moment where two notes differ. Wherever you spot it, that’s your smoking gun: this letter must come before that one. Stack up all these eureka moments and you’ve built a graph. Now: untangle it with topological sort—preferably before a cycle leaves you muttering alien curses at 2 AM.

🛠️ PseudoCode

• Build the graph:
  • For each letter in each word, create a node if it doesn’t exist yet.
  • Go through every adjacent pair of words.
  • Find the first position where the letters differ.
  • Add an edge from the letter in word one to the letter in word two.
  • If word one is longer and is a prefix of word two, return “” immediately (friendly neighborhood prefix error).
• Set up indegrees:
  • Count incoming edges for every unique letter in your alien scroll.
• Topological sort (Kahn’s Algorithm):
  • Queue up all letters with zero incoming edges.
  • Pulll letters off the queue one by one, adding them to your result string.
  • When you remove a letter, drop its edges. If a neighbor’s indegree hits zero, add it to the queue.
  • If you processed all letters without running out of steam, congrats: you have a valid order! Else, cycle alert—return “”.

💻 The Code

import java.util.*;
public class AlienDictionary {
    public String alienOrder(String[] words) {
        Map<character set>> graph = new HashMap<>();
        Map<character integer> indegree = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new HashSet<>());
                indegree.putIfAbsent(c, 0);
            }
        }
        for (int i = 0; i < words.length - 1; ++i) {
            String w1 = words[i], w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            boolean found = false;
            for (int j = 0; j < minLen; ++j) {
                char c1 = w1.charAt(j), c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (graph.get(c1).add(c2)) {
                        indegree.put(c2, indegree.get(c2) + 1);
                    }
                    found = true;
                    break;
                }
            }
            if (!found && w1.length() > w2.length()) return "";
        }
        Queue
<character> q = new LinkedList<>();
        for (char c : indegree.keySet()) {
            if (indegree.get(c) == 0) q.offer(c);
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char c = q.poll(); sb.append(c);
            for (char nei : graph.get(c)) {
                indegree.put(nei, indegree.get(nei) - 1);
                if (indegree.get(nei) == 0) q.offer(nei);
            }
        }
        return sb.length() == indegree.size() ? sb.toString() : "";
    }
}</character></character></character>

⚠️ Pitfalls, Traps & Runtime Smacks

• Prefix trap: If one word is a prefix of the next, but comes first (e.g., “shift” before “shi”), toss your return value right in the cosmic bin. No valid order.
• Cycle mayhem: If the graph doubles back on itself, you’re not ordering letters—you’re organizing a Möbius strip. Return the empty string.
• Efficiency: Build only what you see. No need to catalog the entire Unicode zoo—aliens are efficient creatures.
• Complexity: O(total letters + number of rules). Clean. Predictable. No interstellar taxes applied.

🧠 Interviewer Brain-Tattoo

“If you think the sorted word list is just an alphabet handout, you’re studying for the wrong exam.”