Alien Dictionary, Faster: Primitive Arrays Instead of HashMaps

The Alien Dictionary page solves the problem with Kahn’s algorithm, using a Map<Character, List<Character>> for the graph and a Map<Character, Integer> for the in-degrees. This page runs the same algorithm with primitive arrays instead: an int[] for the in-degrees, a boolean[] for which letters exist, and an array of lists for the graph, all indexed by letter. The algorithm and its $\Theta(V + E)$ runtime are unchanged. What changes is how much work each step costs.

The Code

LeetCode imports java.util.* for you; the import is included here so the code compiles on its own.

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        List<Character>[] graph = new List[26];
        boolean[] existsInGraph = new boolean[26];
        int trueAlphabetSize = 0;
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                int c = word.charAt(i) - 'a';
                if (!existsInGraph[c]) {
                    trueAlphabetSize++;
                    graph[c] = new ArrayList<>();
                    existsInGraph[c] = true;
                }
            }
        }

        for (int k = 0; k < words.length - 1; k++) {
            String firstWord = words[k];
            String nextWord = words[k + 1];
            int i = 0;
            int j = 0;
            while (i < firstWord.length() && j < nextWord.length()) {
                if (firstWord.charAt(i) == nextWord.charAt(j) && (i + 1 < firstWord.length() && j == nextWord.length() - 1)) {
                    return "";  // nextWord is a prefix of firstWord
                } else if (firstWord.charAt(i) != nextWord.charAt(j)) {
                    graph[firstWord.charAt(i) - 'a'].add(nextWord.charAt(j));
                    break;
                }
                i++;
                j++;
            }
        }

        int[] inDegree = new int[26];
        for (int i = 0; i < 26; i++) {
            if (existsInGraph[i]) {
                for (char child : graph[i]) {
                    inDegree[child - 'a']++;
                }
            }
        }

        Queue<Character> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (existsInGraph[i] && inDegree[i] == 0) {
                q.offer((char) ('a' + i));
            }
        }

        int queueCount = 0;
        StringBuilder result = new StringBuilder();
        while (!q.isEmpty()) {
            char curr = q.poll();
            queueCount++;
            result.append(curr);
            for (char next : graph[curr - 'a']) {
                inDegree[next - 'a']--;
                if (inDegree[next - 'a'] == 0) {
                    q.offer(next);
                }
            }
        }
        if (queueCount != trueAlphabetSize) {
            return "";
        }
        return result.toString();
    }
}

The key line is int c = word.charAt(i) - 'a';. Characters in Java are numbers, and 'a' through 'z' are consecutive, so subtracting 'a' turns a letter into an index from 0 to 25: 'a' becomes 0, 'b' becomes 1, and so on up to 'z', which becomes 25. Every array on this page is indexed this way.

Results

On LeetCode (submitted October 24, 2026; 133 of 133 test cases passed):

LeetCode’s timings vary from run to run, and most Java submissions land between 3 and 6 ms, so a single submission is a rough signal. To measure the difference directly, I benchmarked this version against the Map-based Kahn’s solution from the Alien Dictionary page.

Local benchmark. Each input is a list of random words sorted by a random alien alphabet, so every input has a valid answer. Each test was warmed up for 3 seconds so the JIT compiler had optimized both versions, then timed over 21 alternating rounds. The table shows the median time per call and the bytes allocated per call.

I also ran each version in a fresh JVM with no warm-up, the way a single LeetCode submission runs: 133 inputs of 100 words each, 15 runs per version. The median total was 8.6 ms for the HashMap version and 5.9 ms for the array version, about 1.5× faster.

Setup: Java 24 (OpenJDK) on an Apple M4 Pro. Both versions returned a valid alphabet of the same length on all 500 sanity-check inputs.

The biggest speedup is on long words. Step 1 checks every character of every word to see whether that letter is already a vertex. With 100 words of length 100, that is 10,000 checks. In the HashMap version, each one is a containsKey call. In the array version, each one is a single read of existsInGraph[c].

Why It’s Faster

Most of the speed comes from replacing hash lookups with array indexing.

Hash lookups vs. array indexing

Here is what one in-degree update costs in each version:

inDegree.put(b, inDegree.get(b) + 1);  // HashMap version
inDegree[b - 'a']++;                   // array version

The HashMap line does all of this:

1. Box b into a Character object (twice: once for get, once for put).
2. Call hashCode() on it, then scramble the hash bits to pick a bucket.
3. Follow the bucket to a node object, then compare its key with b using equals().
4. Read the Integer value out of the node and unbox it to an int.
5. Add 1, box the result back into an Integer, and repeat steps 2–3 to store it.

The array line computes an address, inDegree + 4 × (b − 'a'), and adds 1 to the number stored there.

The same trade happens everywhere the HashMap version touches a map:

Each HashMap call runs many instructions with several branches. Each array access is a couple of instructions. Kahn’s algorithm makes these calls inside every loop, so the savings add up.

No HashMap entry objects

A HashMap stores each key in its own node object, which holds the key, the value, the hash and a pointer to the next node in the bucket. The HashMap version makes two maps, so each letter gets two nodes. The maps also start with 16 buckets and resize as they fill, so 26 letters cause two resizes per map, and each resize allocates a new bucket table and moves every node into it.

The array version allocates boolean[26], int[26] and List[26] once, at their final size. In the benchmark, this cut the memory allocated per call from 5.6 KB to 3.1 KB. Less allocation means less work for the garbage collector. Most of the remaining 3.1 KB comes from the 26 ArrayLists, the queue and the StringBuilder.

The CPU cache

The CPU reads memory in blocks called cache lines, 64 or 128 bytes at a time depending on the chip, and keeps recently used lines in a small, fast cache. An int[26] is 104 bytes of numbers stored side by side, so the whole array fits in one or two cache lines. Once it is loaded, every in-degree update is a cache hit.

A HashMap spreads the same data across separate objects: a bucket table, a node for each letter, and an Integer object for each value. Reading one in-degree means following pointers from the table to the node to the value. The CPU cannot start loading the next object until it has read the pointer to it, so each lookup waits on a chain of memory reads instead of just one.

To be fair to the HashMap: with only 26 letters, both versions’ data fits in the CPU’s fastest cache. At this size, most of the gain comes from doing fewer steps per lookup, not from avoiding cache misses. The cache advantage of arrays grows as the data grows.

What is still boxed

The array version still uses List<Character> and Queue<Character>, so letters are boxed when added to a list or the queue. This costs less than it looks: Java keeps one shared Character object for each value from 0 to 127, so boxing a lowercase letter reuses an existing object instead of creating a new one. The expensive part of the HashMap version is the hashing and the node objects, not the boxing.

Trade-offs

The array version is faster, but it is harder to read, extend and hand off.

Readability. adj.containsKey(c) says what it means: “is c in the graph?” existsInGraph[firstWord.charAt(i) - 'a'] makes the reader stop and work out that - 'a' turns a letter into an index. Every reader pays that cost, and the next engineer to change the code has to keep the letter-to-index mapping straight in every line. Mixing up next and next - 'a' compiles fine and fails at runtime.

Hidden assumptions. The arrays have exactly 26 slots, so the code assumes every character is a lowercase letter from 'a' to 'z'. LeetCode guarantees this. Real input might not: an uppercase letter, a digit or an accented letter makes c - 'a' negative or larger than 25, and the program crashes with an ArrayIndexOutOfBoundsException. The HashMap version handles any character without changes.

Extending it. If the vertices became words, numbers or objects instead of lowercase letters, the HashMap version would only need new type parameters. The array version would need a new way to turn each vertex into an index, and possibly a different array size.

Abstraction. Map<Character, List<Character>> is the textbook adjacency list, and other engineers recognize it right away. Code built on Map can also be pulled out into a reusable graph class. The array version mixes the graph with the details of how letters are stored.

Which one to use. In most code, the HashMap version is the better default: it is clear, safe for any input, and fast enough. Arrays are worth it when profiling shows that this code is a bottleneck, the keys are known to be small integers or a fixed alphabet, and the speedup matters for the program. Even then, a named constant like ALPHABET_SIZE and a helper like index(char c) can keep most of the speed while making the intent clear.