Is Search Suggestions System easy or hard?

Search Suggestions System is classified as a Medium problem on LeetCode. The core difficulty comes from recognizing that prefix-based queries benefit from a Trie rather than repeatedly scanning the entire product list.

Search Suggestions System Python/Java solution

Python, Java, C++, C#, and JavaScript implementations typically follow two patterns: sorting products and filtering by prefix, or building a Trie that stores up to three suggestions at each node. The Trie implementation is more efficient for large datasets.

How to solve Search Suggestions System in O(n)?

Strict O(n) is not achievable because product strings must be processed character by character. The closest optimal approach is building a Trie in O(n * k) time and then traversing it for each prefix of the search word in O(m * k). This avoids repeatedly scanning the entire product list.

What is the best approach for Search Suggestions System?

The Trie-based approach is generally considered the best solution. It stores product prefixes in a prefix tree and keeps up to three lexicographically smallest suggestions at each node. This allows quick lookup for each character typed in the search word, leading to O(n * k + m * k) time complexity where k is the average product length.

Is Search Suggestions System asked at Google/Amazon/Meta?

Autocomplete and prefix search problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test Trie implementation, efficient prefix search, and system design ideas used in search engines or e-commerce product suggestions.

What data structure is used in Search Suggestions System?

The primary data structure is a Trie (prefix tree), which efficiently stores strings by shared prefixes. Some simpler solutions rely on sorting arrays and performing prefix checks, sometimes combined with binary search to narrow the candidate range.

What is the time complexity of Search Suggestions System?

The optimal Trie solution runs in O(n * k + m * k) time, where n is the number of products, k is the average product length, and m is the search word length. A simpler sorting and scanning approach takes O(n log n + m * n) because it checks the product list for every prefix.

Description Hints 3 Solution Video 13:16

1268. Search Suggestions System

Medium65.1% acceptance19 companies

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Explanation: The only word "havana" will be always suggested while typing the search word.

Constraints:

1 <= products.length <= 1000
1 <= products[i].length <= 3000
1 <= sum(products[i].length) <= 2 * 10⁴
All the strings of products are unique.
products[i] consists of lowercase English letters.
1 <= searchWord.length <= 1000
searchWord consists of lowercase English letters.

Asked at 19 companies

Squarepoint Capital UBS DoorDash Wix Anduril DocuSign Oracle Citadel Twilio Amazon Adobe Bloomberg

+7 more

Tiktok Salesforce PayPal

Google Microsoft Uber Meta

Topics

Array Binary Search Heap (Priority Queue)Sorting String Trie

Hints open one at a time

Hint 1

Brute force is a good choice because length of the string is ≤ 1000.

Hint 2

Binary search the answer.

Hint 3

Use Trie data structure to store the best three matching. Traverse the Trie.

13:16

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

["mobile","mouse","moneypot","monitor","mousepad"]
"mouse"

Input

["havana"]
"havana"

Your code is saved on this device.Solution