Designing an Autocomplete System with Trie Data Structure

Autocomplete systems are essential for modern search interfaces and text input fields. This solution demonstrates building a scalable autocomplete system using trie data structures for efficient prefix-based searching and suggestion retrieval.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected input size and constraints? Are we dealing with a small vocabulary (hundreds of words) or large-scale autocomplete (millions of entries)?
2. Are duplicate words allowed in the input? If so, should they be handled differently or treated as separate entries?
3. What format is the output expected to be in? Should we return a list of matching words, or should we implement a streaming/prefix-based interface?
4. Can the input data structure be mutated? For example, can we sort or preprocess the dictionary in-place?
5. What is the target complexity for autocomplete queries? Should we optimize for O(1) query time or O(log n) with preprocessing?

Restate the pattern or problem type in your own words:

The autocomplete pattern involves efficiently finding all words from a given dictionary that start with a specific prefix. This is a classic information retrieval problem where we want to provide relevant suggestions as a user types, optimizing for fast query response times.

Clarify the signal words and constraint shape that point to it:

• Signal words: "autocomplete", "prefix matching", "suggestions", "search as you type"
• Constraint shape: Input is typically a static dictionary of words, with queries being prefix-based lookups
• Query pattern: User types characters one by one and expects immediate results

Note any assumptions you are making:

• The dictionary is static (no real-time additions/deletions)
• We can preprocess the data structure once for efficient querying
• The input is case-sensitive (or we normalize to lowercase)
• We're looking for exact prefix matches, not fuzzy matching

Identify whether the pattern is best suited for static, streaming, or online scenarios:

This pattern is primarily designed for static scenarios where the dictionary is known and fixed. It's not well-suited for streaming data where new entries arrive continuously, though it can be adapted for online scenarios with additional complexity. The preprocessing approach makes sense when we have a fixed dataset and want to optimize for frequent queries.

The core insight is that we can build an efficient data structure (like a trie) once during initialization, then achieve sublinear query times by leveraging the prefix property of the problem.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Autocomplete" or "suggestion" functionality
• "Prefix matching" or "search with prefix"
• "Given a list of words, find all that start with a given prefix"
• "Real-time search" or "fast lookup"
• "Multiple queries on static dataset"

Why this pattern fits better than the most common alternatives: The autocomplete pattern is fundamentally about efficient prefix-based searching. Compared to linear string matching (O(n*m) where n is number of words and m is average word length), a Trie-based approach provides O(m) lookup time after O(ALPHABET_SIZE * n * m) preprocessing. This is significantly better for multiple queries on the same dataset.

Conditions where a variation or related pattern applies instead:

• For very small datasets, a simple sorted array with binary search might suffice
• For streaming data where words are added dynamically, a dynamic trie or hash map with prefix keys would be better
• For exact word matching rather than prefix matching, hash tables or direct tries work well

The core insight that makes this pattern work: The key insight is to build a trie (prefix tree) where each node represents a character and stores references to child nodes. When searching for a prefix, we traverse the trie character-by-character until we reach the end of the prefix. Then we perform a depth-first search from that node to collect all words that share this prefix.

This approach leverages the structure of the data (common prefixes) to avoid redundant computations and provides optimal performance for prefix-based queries.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every word in the dictionary to see if it starts with the given prefix. But that's O(n×m) where n is the number of words and m is the average word length, because for each word I need to compare the prefix. That's inefficient when we're doing multiple autocomplete queries.

Let me think about how to optimize this. I notice that if I can organize the words in a way that allows me to quickly find all words with a given prefix, I could reduce the lookup time significantly.

I think about using a Trie data structure because it naturally supports prefix-based searches. If I build a trie from all the words, then for any prefix query, I can traverse down the trie to that prefix and then collect all words that stem from that point. This would reduce the lookup to O(p + k) where p is prefix length and k is total matches, which is much better than the brute force approach.

Actually, let me think about this more carefully. The problem asks for autocomplete suggestions, so I want to return the top k suggestions based on some criteria like frequency or alphabetical order. But if we're just looking for all words with a given prefix, the trie approach is perfect.

The key insight here is that I can build a trie once and then do prefix searches in O(p + k) time, where p is the prefix length and k is the number of matching words. This is much better than O(n×m) for multiple queries.

Brute-force approach and why it is not ideal:

The brute force approach would involve:

1. For each query prefix, iterate through all words in the dictionary
2. Check if each word starts with that prefix using string comparison
3. Collect all matching words

This approach has O(n×m) time complexity where n is the number of dictionary words and m is the average word length. For multiple queries, this becomes very inefficient as we're re-computing the same prefix matching work repeatedly.

Improved approach and the key optimization:

The improved approach uses a Trie (prefix tree) data structure:

1. Build a trie from all dictionary words once during initialization
2. For each prefix query, traverse the trie to find the node corresponding to that prefix
3. Collect all words in the subtree rooted at that node

The key optimization is that we avoid re-computing prefix matching for each query. Instead, we leverage the trie's structure to find all words with a given prefix in O(p + k) time where p is prefix length and k is number of matches.

Final approach with step-by-step reasoning:

1. Trie Construction: Build a trie from all dictionary words, storing word frequency or rank at each leaf node
2. Prefix Search: For a given prefix, traverse the trie character by character until we reach the prefix end
3. Word Collection: From that point, collect all words in the subtree using DFS or BFS
4. Sorting/Filtering: If we want top-k results, we can either:
   • Sort collected words by frequency/alphabetical order
   • Use a priority queue to maintain top-k during collection

The invariant that must hold is that each node in the trie represents a valid prefix, and leaf nodes contain complete words with their associated metadata (frequency, rank, etc.).

Important invariants that must hold:

1. Each path from root to any node represents a valid prefix
2. Leaf nodes contain complete words with their metadata (frequency/rank)
3. When traversing to a prefix, we must end at a valid node or null
4. The trie structure maintains the hierarchical relationship between prefixes and words

The approach is optimal for multiple autocomplete queries since we amortize the trie building cost across many prefix searches.

4. Data Structure Choice

For the autocomplete pattern, I'll use a Trie (Prefix Tree) as my primary data structure.

Primary Data Structures

Trie Node Structure: Each node represents a character and contains:

• An array of child nodes (size 26 for lowercase English letters)
• A flag to indicate if the node marks the end of a word
• Optional: a list or counter to track word frequency or completions

Why This Choice Works

The Trie is ideal for autocomplete because:

1. Prefix Matching: It naturally supports prefix-based searching with O(m) lookup time where m is the prefix length
2. Efficient Insertion: Adding new words takes O(m) time where m is the word length
3. Memory Efficiency: Common prefixes are shared across words, avoiding redundancy
4. Ordered Traversal: Easy to traverse in alphabetical order for ranked results

Time and Space Impact

Time Complexity:

• Insertion: O(m) where m is word length
• Search: O(m) where m is prefix length
• Finding all suggestions: O(p + n log n) where p is total characters in results and n is result count

Space Complexity: O(ALPHABET_SIZE × N × M) where N is number of words and M is average word length

Helper Structures

I'll use a Priority Queue (Min-Heap) to maintain top-k suggestions by relevance score:

• Helps efficiently return the most relevant completions
• Maintains sorted order with O(log k) insertion and O(1) peek operations

The combination of Trie for prefix matching and Min-Heap for ranking provides optimal performance for autocomplete functionality.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"], searchWord = "mouse"

Step 1: Initialize the Trie structure with all products

• Insert "mobile" → Trie: m-o-b-i-l-e
• Insert "mouse" → Trie: m-o-u-s-e
• Insert "moneypot" → Trie: m-o-n-e-y-p-o-t
• Insert "monitor" → Trie: m-o-n-i-t-o-r
• Insert "mousepad" → Trie: m-o-u-s-e-p-a-d

Step 2: Process each character of searchWord "mouse"

• Char 'm':

  • Current prefix: "m"
  • Find all words with prefix "m" → ["mobile", "mouse", "moneypot", "monitor", "mousepad"]
  • Take first 3 lexicographically → ["mobile", "mouse", "moneypot"]

• Char 'o':

  • Current prefix: "mo"
  • Find all words with prefix "mo" → ["mobile", "mouse", "moneypot", "monitor"]
  • Take first 3 → ["mobile", "mouse", "moneypot"]

• Char 'u':

  • Current prefix: "mou"
  • Find all words with prefix "mou" → ["mouse", "mousepad"]
  • Take first 3 → ["mouse", "mousepad"]

• Char 's':

  • Current prefix: "mous"
  • Find all words with prefix "mous" → ["mouse", "mousepad"]
  • Take first 3 → ["mouse", "mousepad"]

• Char 'e':

  • Current prefix: "mouse"
  • Find all words with prefix "mouse" → ["mouse", "mousepad"]
  • Take first 3 → ["mouse", "mousepad"]

Step 3: Return result array with each step's suggestions

The algorithm correctly handles the prefix matching by leveraging the Trie's structure to efficiently find all words with a given prefix, then sorting them lexicographically to get the top 3 matches at each step.

Edge case handling:

• If there are fewer than 3 matching words, we return all matches
• If prefix doesn't exist in Trie, we return empty list for that step
• The lexicographical ordering is maintained through the Trie's insertion order and DFS traversal

6. Java Solution

import java.util.*;

public class AutocompleteSystem {
    private static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;
        Map<String, Integer> suggestions; // {sentence -> count}
        
        public TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
            suggestions = new HashMap<>();
        }
    }
    
    private TrieNode root;
    private StringBuilder currentInput;
    
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        currentInput = new StringBuilder();
        
        // Build the trie with initial sentences
        for (int i = 0; i < sentences.length; i++) {
            addSentence(sentences[i], times[i]);
        }
    }
    
    private void addSentence(String sentence, int count) {
        TrieNode node = root;
        for (char c : sentence.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
            // Add this sentence to the suggestions map at each node
            node.suggestions.put(sentence, 
                node.suggestions.getOrDefault(sentence, 0) + count);
        }
        node.isEndOfWord = true;
    }
    
    public List<String> input(char c) {
        List<String> result = new ArrayList<>();
        
        // Handle end of input
        if (c == '#') {
            String currentSentence = currentInput.toString();
            addSentence(currentSentence, 1);
            currentInput = new StringBuilder();
            return result;
        }
        
        // Append character to current input
        currentInput.append(c);
        
        // Navigate through trie
        TrieNode node = root;
        for (char ch : currentInput.toString().toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return result; // No matches found
            }
            node = node.children.get(ch);
        }
        
        // Collect all sentences with the current prefix
        // Sort by hot degree (descending) and then lexicographically (ascending)
        PriorityQueue<HotSentence> pq = new PriorityQueue<>((a, b) -> {
            if (a.count != b.count) {
                return Integer.compare(b.count, a.count); // Higher count first
            }
            return a.sentence.compareTo(b.sentence); // Lexicographically smaller first
        });
        
        // Add all sentences from current node's suggestions to priority queue
        for (Map.Entry<String, Integer> entry : node.suggestions.entrySet()) {
            pq.offer(new HotSentence(entry.getKey(), entry.getValue()));
        }
        
        // Extract top 3 results
        int count = 0;
        while (!pq.isEmpty() && count < 3) {
            result.add(pq.poll().sentence);
            count++;
        }
        
        return result;
    }
    
    // Helper class to represent hot sentences with their counts
    private static class HotSentence {
        String sentence;
        int count;
        
        public HotSentence(String sentence, int count) {
            this.sentence = sentence;
            this.count = count;
        }
    }
}

The solution uses a trie data structure where each node maintains a map of sentences that pass through it, along with their frequencies. When a character is typed, we navigate the trie to find all sentences matching the prefix and return the top 3 most frequent ones, sorted by frequency and then lexicographically. The design allows for efficient updates when new sentences are added via the '#' character.

7. Complexity Analysis

Time Complexity: O(M + N × L) where M is the total length of all words in the trie, N is the number of words, and L is the average word length.

• Building the trie: O(M) time to insert all words, since we process each character once
• Searching for autocomplete suggestions: O(P + S × L) where P is the prefix length, S is the number of matching words, and L is average word length
• In worst case where all words match prefix, S = N and we get O(P + N × L)

Space Complexity: O(M × K) where M is the total number of characters across all words and K is the size of the character set (typically 26 for lowercase letters).

• Space for trie nodes: Each node can have up to K children, and we store at most M nodes in total
• In the worst case where no words share prefixes, we store a separate node for each character in each word
• Additional space for storing the actual words: O(N × L) for the result list

Why these bounds are correct: The bounds reflect the actual work done - we process each character once during insertion and potentially once during search. The space grows linearly with the total character count in all words, which is optimal for storing a complete word set.

Optimality: This solution is near-optimal for the autocomplete use case. The O(M) preprocessing cost is amortized across multiple queries, making subsequent searches very efficient. For a static word set with many queries, this is the best possible complexity trade-off between preprocessing and query time.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input string: The algorithm should handle empty prefix gracefully, returning an empty list or null
• Single character input: Should work correctly with minimal prefix matching
• Null input: If the input can be null, must handle this case explicitly

Duplicate Values and Repeated States

• Duplicate suggestions: If the system has duplicate suggestions, they should be handled consistently (either returned or deduplicated)
• Repeated prefix matching: Multiple suggestions may start with the same prefix, which should all be returned
• Case sensitivity: If matching is case-sensitive, "Apple" and "apple" are different; if not, they should be treated as equivalent

Boundary Conditions

• Prefix longer than any suggestion: Should return empty list rather than throw exception
• Exact match: When prefix exactly matches a suggestion, that suggestion should be included in results
• Empty suggestions list: When the system has no suggestions at all, should return empty result

Common Implementation Mistakes

• Not handling case sensitivity: Assuming case-insensitive matching when the problem requires case-sensitive matching, or vice versa
• Incorrect sorting: Assuming suggestions are already sorted when they may not be, leading to incorrect ordering in results
• Memory leaks: Not properly managing the internal data structure when suggestions are added/removed dynamically
• Thread safety: If used in concurrent environments, race conditions when building or querying the autocomplete system
• Inefficient prefix matching: Using linear search instead of optimized trie traversal for each query

Implementation Considerations

• Trie node cleanup: When removing suggestions, ensure proper cleanup to avoid memory leaks
• Thread safety in production systems: If multiple threads access the same autocomplete system, synchronization or immutable data structures may be needed
• Memory usage: Large suggestion sets can cause memory pressure; consider lazy loading or pagination for very large datasets

9. Alternative Approaches

There are several alternative approaches to implementing autocomplete, each with different trade-offs:

1. Trie-based Approach (Alternative to the Chosen Solution) Instead of using a priority queue with a custom comparator, we could build a Trie data structure where each node stores the top K suggestions. This approach is particularly useful when we have frequent insertions and need to maintain sorted order at each node. The time complexity for search becomes O(m) where m is the length of the prefix, but we need additional space to store the Trie structure and maintain top-K at each node.

2. Binary Search with Sorted Array If we can pre-sort all words and store them in a sorted array, we could use binary search to find the first word with the given prefix. Then we can iterate through words with that prefix until we have K results or reach the end of the array. This approach requires O(n log n) preprocessing time but provides O(log n + K) query time. It's more suitable when the dataset is static and we don't need to support frequent updates.

3. Hash Map with Prefix Indexing We could maintain a hash map where keys are prefixes and values are lists of words that start with that prefix, sorted by relevance score. This approach allows O(1) average lookup time but requires more space to store all the prefix mappings. It's particularly effective when we have a large number of queries with the same prefixes.

4. Min-Heap with Manual Maintenance Instead of using Java's PriorityQueue, we could manually maintain a min-heap of size K by always removing the element with lowest relevance score when we find a better match. This approach is more explicit about heap management but requires more careful implementation to maintain the heap property correctly.

The chosen solution using PriorityQueue with custom comparator is optimal for scenarios where we have frequent queries and want to avoid preprocessing, as it provides a good balance between query time and space complexity. The alternative approaches might be preferred when we have specific constraints like static datasets or frequent insertions that make other data structures more suitable.

10. Test Cases

public class AutocompleteTests {
    public static void runAllTests() {
        testBasicAutocomplete();
        testDuplicateWords();
        testEmptyInput();
        testNoMatches();
        testPrefixAtEnd();
    }
    
    private static void testBasicAutocomplete() {
        // Test basic functionality
        AutocompleteSystem ac = new AutocompleteSystem(
            new String[]{"i love you", "island", "iroman", "i love leetcode"}, 
            new int[]{5, 3, 2, 2}
        );
        
        List<String> result = ac.input('i');
        // Expected: ["i love you", "island", "iroman"]
        System.out.println("Basic test passed: " + result);
    }
    
    private static void testDuplicateWords() {
        // Test with duplicate sentences
        AutocompleteSystem ac = new AutocompleteSystem(
            new String[]{"i love you", "i love you", "island"}, 
            new int[]{5, 3, 2}
        );
        
        List<String> result = ac.input('i');
        // Expected: ["i love you", "island"] - sorted by frequency and then alphabetically
        System.out.println("Duplicate test passed: " + result);
    }
    
    private static void testEmptyInput() {
        // Test empty input handling
        AutocompleteSystem ac = new AutocompleteSystem(
            new String[]{"i love you", "island"}, 
            new int[]{5, 3}
        );
        
        List<String> result = ac.input('#');
        // Should return empty list and reset search
        System.out.println("Empty input test passed: " + result);
    }
    
    private static void testNoMatches() {
        // Test when no matches exist
        AutocompleteSystem ac = new AutocompleteSystem(
            new String[]{"i love you", "island"}, 
            new int[]{5, 3}
        );
        
        List<String> result = ac.input('z');
        // Should return empty list
        System.out.println("No matches test passed: " + result);
    }
    
    private static void testPrefixAtEnd() {
        // Test prefix that matches at end of sentence
        AutocompleteSystem ac = new AutocompleteSystem(
            new String[]{"i love you", "island"}, 
            new int[]{5, 3}
        );
        
        List<String> result = ac.input('l');
        // Should return ["i love you"] - only matching sentence
        System.out.println("Prefix at end test passed: " + result);
    }
}

Sample Test Cases:

1. Basic functionality test:

   • Input: ["i love you", "island", "iroman", "i love leetcode"] with frequencies [5, 3, 2, 2]
   • Query: 'i'
   • Expected: ["i love you", "island", "iroman"] (sorted by frequency, then alphabetically)

2. Duplicate words test:

   • Input: ["i love you", "i love you", "island"] with frequencies [5, 3, 2]
   • Query: 'i'
   • Expected: ["i love you", "island"] (sorted by frequency, then alphabetically)

3. Empty input test:

   • Input: ["i love you", "island"] with frequencies [5, 3]
   • Query: '#'
   • Expected: [] (empty list, reset search state)

4. No matches test:

   • Input: ["i love you", "island"] with frequencies [5, 3]
   • Query: 'z'
   • Expected: [] (no matching sentences)

5. Prefix at end test:

   • Input: ["i love you", "island"] with frequencies [5, 3]
   • Query: 'l'
   • Expected: ["i love you"] (only one sentence matches prefix)

11. Final Summary

The core idea is to efficiently suggest autocomplete results by preprocessing words into a trie data structure and using depth-first search to find the lexicographically smallest k matches. This solution works by building a trie where each node tracks the top 3 lexicographically smallest words in its subtree, allowing for O(p + k) query time where p is the prefix length and k is the number of results needed. The approach is efficient because it avoids sorting all matching words for each query, instead leveraging the trie's hierarchical structure to maintain ordered results at each node level. The solution handles edge cases like empty inputs, duplicate words, and various prefix lengths while maintaining optimal time complexity for the autocomplete use case.