Skip to main content
Talentd

Design Search Autocomplete System - Solution & Explanation

HardPremiumFree on FleetCodeStringDepth-First SearchDesignTrie7 min readAsked at: Amazon, Microsoft, Meta +9
Practice this problem

Problem Statement

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#').

You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed.

Here are the specific rules:

  • The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
  • The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
  • If less than 3 hot sentences exist, return as many as you can.
  • When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Implement the AutocompleteSystem class:

  • AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
  • List<String> input(char c) This indicates that the user typed the character c.
    • Returns an empty array [] if c == '#' and stores the inputted sentence in the system.
    • Returns the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.

 

Example 1:

Input
["AutocompleteSystem", "input", "input", "input", "input"]
[[["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
Output
[null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]

Explanation
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]. There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ".
obj.input("a"); // return []. There are no sentences that have prefix "i a".
obj.input("#"); // return []. The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.

 

Constraints:

  • n == sentences.length
  • n == times.length
  • 1 <= n <= 100
  • 1 <= sentences[i].length <= 100
  • 1 <= times[i] <= 50
  • c is a lowercase English letter, a hash '#', or space ' '.
  • Each tested sentence will be a sequence of characters c that end with the character '#'.
  • Each tested sentence will have a length in the range [1, 200].
  • The words in each input sentence are separated by single spaces.
  • At most 5000 calls will be made to input.

Approach Overview

Problem Overview: Design a search autocomplete system that suggests the top 3 historical sentences matching the current prefix as the user types characters. Suggestions are ranked by frequency and then lexicographically when frequencies tie.

Approach 1: Brute Force Prefix Scan + Sorting (Time: O(n log n) per query, Space: O(n))

Store every sentence and its frequency in a hash map. Each time the user types a character, build the current prefix and iterate through all stored sentences to find matches using startswith. Collect matching sentences, then sort them by frequency (descending) and lexicographical order (ascending). Return the top three results. This approach is simple to implement and works for small datasets, but it scales poorly because every keystroke scans the entire sentence list.

Approach 2: Trie with Frequency Map and Heap (Time: O(p + k log m) per query, Space: O(n * L))

Use a Trie to index all sentences by prefix. Each Trie node represents a character and allows fast traversal to the prefix node in O(p) where p is the prefix length. From that node, perform a Depth-First Search to collect candidate sentences stored under that prefix. Use a Heap (Priority Queue) to keep the top 3 sentences ranked by frequency and lexicographical order. This significantly reduces the search space compared to scanning all sentences.

Approach 3: Trie with Cached Top-3 Suggestions (Time: O(p) per query, Space: O(n * L))

An optimized design stores the top three suggestions directly at each Trie node. During insertion or frequency updates, update the node's top-3 list based on frequency and lexicographical ordering. When a user types a character, simply traverse the Trie and return the cached list stored at that node. This removes the need for DFS or heap operations during queries, making lookups extremely fast while slightly increasing update complexity and memory usage.

Recommended for interviews: Interviewers typically expect the Trie-based design. Starting with the brute force solution demonstrates understanding of the ranking rules. The optimized Trie approach shows system design thinking, efficient prefix search, and practical use of data structures for real-time suggestion systems.

Solution

Code

PythonJava

Python

Java

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Prefix Scan + SortO(n log n) per queryO(n)Simple implementation when dataset is small
Trie + DFS + HeapO(p + k log m)O(n * L)General scalable solution for prefix search with ranking
Trie with Cached Top-3O(p)O(n * L)High-performance autocomplete systems with frequent queries

Video Solution

LeetCode 642. Design Search Autocomplete System Explanation and Solution • happygirlzt • 17,365 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Search Autocomplete System easy or hard?
Design Search Autocomplete System is classified as a Hard problem because it combines Trie design, ranking logic, and dynamic updates to sentence frequencies. Efficient implementations require careful data structure choices.
Design Search Autocomplete System Python/Java solution
A typical Python or Java implementation builds a Trie where each node stores children and suggestion metadata. During typing, the system traverses the Trie using the current prefix and retrieves the top three ranked sentences.
How to solve Design Search Autocomplete System in O(p)?
Store the top three suggestions directly at each Trie node. While inserting sentences or updating frequencies, maintain a sorted list of the best candidates at every node. When a user types characters, traverse the Trie to the prefix node and return the stored list in O(p) time.
What is the best approach for Design Search Autocomplete System?
The most efficient approach uses a Trie where each node represents a prefix and stores the top 3 suggestions for that prefix. Query time becomes O(p) where p is the prefix length. This design avoids scanning the entire dataset and is commonly expected in interviews.
Is Design Search Autocomplete System asked at Google/Amazon/Meta?
Autocomplete system design problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of Trie structures, ranking systems, and efficient real-time query processing.
What data structure is used in Design Search Autocomplete System?
The core data structure is a Trie for efficient prefix lookup. Additional structures such as heaps (priority queues) or sorted lists are used to maintain the top suggestions ranked by frequency and lexicographical order.
What is the time complexity of Design Search Autocomplete System?
Using a Trie with cached top suggestions, each query runs in O(p) time where p is the length of the typed prefix. Building the Trie requires O(n * L) time where n is the number of sentences and L is the average sentence length.

Ready to solve this problem?

Practice Design Search Autocomplete System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Implement Trie (Prefix Tree)