Editorial
Core insight
Design Search Autocomplete System · Design Patterns
Core Insight for Design Search Autocomplete System
The brute force approach is inefficient because it searches the entire dataset repeatedly. The core insight is to organize the data in a way that allows us to access only the relevant subset of sentences that match the current prefix.
A Trie (Prefix Tree) is the ideal data structure for this.
- Shared Prefixes: Sentences like "island" and "islander" share the path
i -> s -> l -> a -> n -> d. We traverse this path once. - State Management: As the user types, we can maintain a pointer to the current node in the Trie. When the user types the next character, we simply move the pointer one step deeper.
- Subtree Search: Once we are at the node representing the current prefix, all possible completions exist within the subtree rooted at that node. We only need to traverse this smaller subtree to find candidates, rather than the entire database.
Visual Description:
Imagine the Trie as a directory structure. The root is the main folder. Typing 'a' opens folder 'a'. Typing 'b' then looks for folder 'b' inside 'a'. If we are inside folder a/b, the only files (sentences) we can possibly find are those contained within. We don't need to look at folders starting with 'z'. Each file (completed sentence) has a "weight" (frequency) written on it. We collect the heaviest files in the current directory and sub-directories.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 642: Design Search Autocomplete System Solution & Explanation
Problem Overview
TL;DR: The optimal solution utilizes a Trie (Prefix Tree) to store historical sentences and their frequencies, allowing for efficient prefix-based lookups and dynamic updates as the user types.
In LeetCode 642, we are tasked with building a search autocomplete system similar to those found in search engines. The system is initialized with a list of historical sentences and their typing frequencies. As a user types characters, the system must return the top 3 historical sentences that start with the current input prefix. If the user completes a sentence (indicated by #), the system must record this new sentence or update its frequency in the database.
The results for any prefix query must be sorted primarily by frequency (descending) and secondarily by lexicographical order (ascending).
Brute Force Approach for Design Search Autocomplete System
The naive approach relies on storing all historical sentences and their counts in a hash map (Dictionary in Python, HashMap in Java/C++).
When the input(c) method is called:
- We append the character
cto a string buffer maintaining the current query. - We iterate through every key in the hash map.
- We check if the key starts with the current string buffer.
- If it does, we add it to a list of candidates.
- Finally, we sort the list of candidates and return the top 3.
1# Pseudo-code for Brute Force
2class AutocompleteSystem:
3 def __init__(self, sentences, times):
4 self.map = {s: t for s, t in zip(sentences, times)}
5 self.current_query = ""
6
7 def input(self, c):
8 if c == '#':
9 self.map[self.current_query] += 1
10 self.current_query = ""
11 return []
12
13 self.current_query += c
14 matches = []
15 for sentence, freq in self.map.items():
16 if sentence.startswith(self.current_query):
17 matches.append((freq, sentence))
18
19 # Sort by freq desc, then sentence asc
20 matches.sort(key=lambda x: (-x[0], x[1]))
21 return [m[1] for m in matches[:3]]Time Complexity Analysis:
If there are historical sentences and the average length is , the input operation takes , where is the number of matches.
Why it fails: While this might pass for very small constraints (like ), it is not a scalable system design. In a real-world scenario with millions of sentences, iterating through the entire database for every single keystroke is prohibitively slow. It fails to utilize the structural property of the strings (shared prefixes).
Algorithm Strategy: Design Patterns
We will design a class that encapsulates a Trie and the current input state.
-
Trie Node Structure: Each node contains:
- A map/array to children nodes (mapped by character).
- A frequency count (initialized to 0). If the count is , this node represents the end of a sentence.
-
System State:
root: The root of the Trie.current_string: A buffer to store what the user has typed so far (needed for insertion when#is pressed).- Optionally, a
current_nodepointer to optimize traversal (though re-traversing from root for the current short prefix is also acceptable and simpler to implement).
-
Handling Input:
- Character Input: Append to
current_string. Traverse the Trie to the node matching thecurrent_string. Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from that node to collect all valid sentences in the subtree. - Terminator (
#): Insertcurrent_stringinto the Trie. Increment the frequency at the terminal node. Resetcurrent_stringto empty. Return an empty list.
- Character Input: Append to
-
Sorting: The collection of sentences found during the DFS is sorted by frequency (descending) and then lexicographically (ascending). We take the top 3.
Execution Flow
-
Initialization:
- Create a root TrieNode.
- Iterate through the input
sentencesandtimes. - For each sentence, insert it into the Trie character by character.
- At the last node of the sentence, set
node.frequency = times[i].
-
Processing
input(c)wherec != '#':- Append
ctocurrent_string. - Traverse from
rootfollowing the path defined bycurrent_string. - Case A (Prefix not found): If the path breaks (child doesn't exist), return an empty list (no historical sentences match).
- Case B (Prefix found): We arrive at a node
target_node.- Initiate a DFS starting at
target_node. - During DFS, if a node has
frequency > 0, add(frequency, full_sentence_string)to a results list. - Continue traversing all children.
- After DFS, sort the results list: primary key
-frequency, secondary keysentence. - Return the first 3 elements.
- Initiate a DFS starting at
- Append
-
Processing
input('#'):- This marks the end of a user's sentence.
- Traverse the Trie with
current_string(creating new nodes if they don't exist). - Increment the frequency at the final node.
- Reset
current_stringto"". - Return
[].
Proof of Correctness
The correctness relies on the Trie property: any descendant of the node representing string must have as a prefix. By traversing to the node corresponding to the user's input and searching only that subtree, we guarantee that all returned sentences start with the required prefix. The sorting step explicitly enforces the problem's ordering constraints (frequency then lexicographical), ensuring the "Top 3" requirement is met deterministically.
Pattern Reuse Notes
The Design pattern with a focus on data structure composition is critical for many system design interviews.
- LeetCode 146: LRU Cache - Uses a Hash Map combined with a Doubly Linked List to manage state and ordering efficiently.
- LeetCode 155: Min Stack - Uses parallel stacks or node metadata to retrieve the minimum element in .
- LeetCode 225: Implement Stack using Queues - Manipulates standard data structures to mimic behavior of another.
- LeetCode 232: Implement Queue using Stacks - Similar to 225, focuses on API constraints and amortized complexity.
In all these problems, the key is wrapping standard data structures in a class to enforce specific behavioral constraints or performance requirements.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 642
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8class TrieNode {
9public:
10 unordered_map<char, TrieNode*> children;
11 int times;
12
13 TrieNode() : times(0) {}
14};
15
16class AutocompleteSystem {
17private:
18 TrieNode* root;
19 string current_query;
20
21 void insert(string& s, int time) {
22 TrieNode* node = root;
23 for (char c : s) {
24 if (!node->children.count(c)) {
25 node->children[c] = new TrieNode();
26 }
27 node = node->children[c];
28 }
29 node->times += time;
30 }
31
32 // DFS to find all sentences in the subtree
33 void dfs(TrieNode* node, string path, vector<pair<int, string>>& results) {
34 if (node->times > 0) {
35 results.push_back({node->times, path});
36 }
37 for (auto& pair : node->children) {
38 dfs(pair.second, path + pair.first, results);
39 }
40 }
41
42public:
43 AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
44 root = new TrieNode();
45 current_query = "";
46 for (int i = 0; i < sentences.size(); ++i) {
47 insert(sentences[i], times[i]);
48 }
49 }
50
51 vector<string> input(char c) {
52 if (c == '#') {
53 insert(current_query, 1);
54 current_query = "";
55 return {};
56 }
57
58 current_query += c;
59 TrieNode* node = root;
60
61 // Traverse to the node representing current_query
62 for (char ch : current_query) {
63 if (!node->children.count(ch)) {
64 return {}; // Prefix not found
65 }
66 node = node->children[ch];
67 }
68
69 // Collect all sentences with this prefix
70 vector<pair<int, string>> results;
71 dfs(node, current_query, results);
72
73 // Sort: Descending by freq, Ascending by lexicographical
74 sort(results.begin(), results.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
75 if (a.first != b.first) {
76 return a.first > b.first;
77 }
78 return a.second < b.second;
79 });
80
81 vector<string> top3;
82 for (int i = 0; i < min((int)results.size(), 3); ++i) {
83 top3.push_back(results[i].second);
84 }
85 return top3;
86 }
87};Java Solution for LeetCode 642
1import java.util.*;
2
3class AutocompleteSystem {
4
5 class TrieNode {
6 Map<Character, TrieNode> children;
7 int times;
8
9 public TrieNode() {
10 children = new HashMap<>();
11 times = 0;
12 }
13 }
14
15 private TrieNode root;
16 private StringBuilder currentQuery;
17
18 public AutocompleteSystem(String[] sentences, int[] times) {
19 root = new TrieNode();
20 currentQuery = new StringBuilder();
21 for (int i = 0; i < sentences.length; i++) {
22 insert(sentences[i], times[i]);
23 }
24 }
25
26 private void insert(String s, int time) {
27 TrieNode node = root;
28 for (char c : s.toCharArray()) {
29 node.children.putIfAbsent(c, new TrieNode());
30 node = node.children.get(c);
31 }
32 node.times += time;
33 }
34
35 public List<String> input(char c) {
36 if (c == '#') {
37 insert(currentQuery.toString(), 1);
38 currentQuery = new StringBuilder();
39 return new ArrayList<>();
40 }
41
42 currentQuery.append(c);
43 TrieNode node = root;
44
45 // Traverse to current prefix
46 for (int i = 0; i < currentQuery.length(); i++) {
47 char ch = currentQuery.charAt(i);
48 if (!node.children.containsKey(ch)) {
49 return new ArrayList<>();
50 }
51 node = node.children.get(ch);
52 }
53
54 // Collect matches
55 List<NodeFreq> matches = new ArrayList<>();
56 dfs(node, currentQuery.toString(), matches);
57
58 // Sort
59 Collections.sort(matches, (a, b) -> {
60 if (a.times != b.times) {
61 return b.times - a.times; // Descending freq
62 }
63 return a.sentence.compareTo(b.sentence); // Ascending lex
64 });
65
66 List<String> result = new ArrayList<>();
67 for (int i = 0; i < Math.min(3, matches.size()); i++) {
68 result.add(matches.get(i).sentence);
69 }
70 return result;
71 }
72
73 private void dfs(TrieNode node, String path, List<NodeFreq> matches) {
74 if (node.times > 0) {
75 matches.add(new NodeFreq(path, node.times));
76 }
77 for (char key : node.children.keySet()) {
78 dfs(node.children.get(key), path + key, matches);
79 }
80 }
81
82 class NodeFreq {
83 String sentence;
84 int times;
85 public NodeFreq(String s, int t) {
86 this.sentence = s;
87 this.times = t;
88 }
89 }
90}Python Solution for LeetCode 642
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.times = 0
5
6class AutocompleteSystem:
7
8 def __init__(self, sentences: list[str], times: list[int]):
9 self.root = TrieNode()
10 self.current_query = ""
11 for s, t in zip(sentences, times):
12 self.insert(s, t)
13
14 def insert(self, sentence, time):
15 node = self.root
16 for char in sentence:
17 if char not in node.children:
18 node.children[char] = TrieNode()
19 node = node.children[char]
20 node.times += time
21
22 def input(self, c: str) -> list[str]:
23 if c == '#':
24 self.insert(self.current_query, 1)
25 self.current_query = ""
26 return []
27
28 self.current_query += c
29 node = self.root
30
31 # Navigate to current prefix
32 for char in self.current_query:
33 if char not in node.children:
34 return []
35 node = node.children[char]
36
37 # DFS to find all sentences in subtree
38 matches = []
39 self.dfs(node, self.current_query, matches)
40
41 # Sort: Primary key freq (desc), Secondary key string (asc)
42 # Python sort is stable, but we use a tuple key for explicit ordering
43 matches.sort(key=lambda x: (-x[0], x[1]))
44
45 return [sentence for freq, sentence in matches[:3]]
46
47 def dfs(self, node, path, matches):
48 if node.times > 0:
49 matches.append((node.times, path))
50
51 for char, child_node in node.children.items():
52 self.dfs(child_node, path + char, matches)