Design Search Autocomplete System
Hard · Tries · Explanation and code example
Optimize with Heap
How it works
Sorting all matching sentences every time is expensive when there are many matches. Since we only need the top 3 results, we can use a heap to find them more efficiently. By building a min-heap of size 3, we process each sentence once and keep only the best candidates. In languages with linear-time heapify (like Python's heapq.nsmallest), this gives a performance boost over full sorting.
Steps
- Initialization: Same as before: build the trie with sentence counts at each node. Store counts as negative values so that a min-heap naturally gives us the highest frequencies.
- input(c): If
cis#, add the completed sentence to the trie, reset state, and return empty. - Otherwise, append
cand navigate the trie. If the character does not exist, go to the dead node and return empty. - At the current node, use a heap to find the top
3sentences. With negative counts, the smallest values represent the highest frequencies. Extract up to3items and return them. - addToTrie(sentence, count): Walk through each character, creating nodes as needed. Subtract (rather than add) the count so that smaller numeric values indicate higher popularity.
Complexity
This analysis will assume that you have access to a linear time heapify method, like in the Python implementation.
-
Time complexity:
O(n × k + m × (n + frac{m}{k}))constructor:- We initialize the trie, which costs
O(n × k)as we iterate over each character in each sentence.
input:- We add a character to
currSentenceand the trie, both costO(1). Next, we fetch the sentences in the current node. Initially, a node could holdO(n)sentences. After we callinputmtimes, we could addfrac{m}{k}new sentences. Overall, there could be up toO(n + frac{m}{k})sentences. We heapify these sentences and find the best 3 in linear time, which costsO(n + frac{m}{k}). - The work done in the other cases (like adding a new sentence to the trie) will be dominated by this.
inputis calledmtimes, which gives us a total ofO(m × (n + frac{m}{k})).
- We initialize the trie, which costs
-
Space complexity:
O(k × (n × k + m))
Where
nis the length ofsentences,kis the average length of all sentences, andmis the number of timesinputis called.
Things to watch for
Forgetting to Reset State on '#'
When the user presses #, you must add the completed sentence to the trie, reset the current sentence, and return the trie pointer to root. Missing any of these steps causes incorrect behavior on subsequent inputs.
Not Handling Non-Existent Prefix Path
When a character doesn't exist in the current node's children, the system should return empty results for all subsequent characters until # is pressed. Using a "dead" node pattern handles this cleanly.
Wrong Sorting Order for Results
Results must be sorted by frequency (highest first), then alphabetically for ties. Reversing this order or sorting in the wrong direction gives incorrect top-3 results.
Not Storing Sentence at Every Node Along Path
Each trie node must store all sentences that pass through it, not just at the leaf. Otherwise, prefix queries won't find matching sentences.
Returning More Than 3 Results
The problem requires returning at most 3 results. Forgetting to limit the output or using the wrong slice gives incorrect answers.
Python code example
from typing import List
from collections import defaultdict
import heapq
class TrieNode:
def __init__(self):
self.children = {}
self.sentences = defaultdict(int)
class AutocompleteSystem:
def __init__(self, sentences: List[str], times: List[int]):
self.root = TrieNode()
for sentence, count in zip(sentences, times):
self.add_to_trie(sentence, count)
self.curr_sentence = []
self.curr_node = self.root
self.dead = TrieNode()
def input(self, c: str) -> List[str]:
if c == "#":
curr_sentence = "".join(self.curr_sentence)
self.add_to_trie(curr_sentence, 1)
self.curr_sentence = []
self.curr_node = self.root
return []
self.curr_sentence.append(c)
if c not in self.curr_node.children:
self.curr_node = self.dead
return []
self.curr_node = self.curr_node.children[c]
items = [(val, key) for key, val in self.curr_node.sentences.items()]
ans = heapq.nsmallest(3, items)
return [item[1] for item in ans]
def add_to_trie(self, sentence, count):
node = self.root
for c in sentence:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.sentences[sentence] -= count
C++ code example
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
unordered_map<string, int> sentences;
TrieNode() {}
};
class AutocompleteSystem {
private:
TrieNode* root;
TrieNode* currNode;
TrieNode* dead;
string currSentence;
void addToTrie(const string& sentence, int count) {
TrieNode* node = root;
for (char c : sentence) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
node->sentences[sentence] -= count;
}
}
public:
AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
root = new TrieNode();
dead = new TrieNode();
currNode = root;
currSentence = "";
for (int i = 0; i < sentences.size(); i++) {
addToTrie(sentences[i], times[i]);
}
}
vector<string> input(char c) {
if (c == '#') {
addToTrie(currSentence, 1);
currSentence = "";
currNode = root;
return {};
}
currSentence += c;
if (currNode->children.find(c) == currNode->children.end()) {
currNode = dead;
return {};
}
currNode = currNode->children[c];
vector<pair<int, string>> items;
for (const auto& [sentence, count] : currNode->sentences) {
items.push_back({count, sentence});
}
// O(n log n) sort instead of O(n) heapify - main performance difference from Python
sort(items.begin(), items.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
vector<string> ans;
for (int i = 0; i < min(3, (int)items.size()); i++) {
ans.push_back(items[i].second);
}
return ans;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.