Search Suggestions System solution and explanation
Google
9 more videos on this problem
Search Suggestions System - Leetcode 1268 - PythonNeetCode · 13:16 · 60K views
LeetCode 1268. Search Suggestions System - Interview Prep Ep 103Fisher Coder · 20:34 · 8K views
Search Suggestions System | Leetcode 1268 | Trie | Binary SeachAyushi Sharma · 24:16 · 6K views
LeetCode 1268. Search Suggestions System Explanation and Solutionhappygirlzt · 11:59 · 5K views
Leetcode - Search Suggestions System (Python)Timothy H Chang · 4:55 · 3K views
Search Suggestions System | LeetCode 1268 | Coders CampCoders Camp · 10:17 · 1K views
LeetCode 1268 Search Suggestions System - Google, Amazon, Apple Interview Question SolvedAlgorithmicIQ · 18:07 · 815 views
Leetcode 1268 Search Suggestions System | TreeMap | Checkout Coding Decoded SDE SheetCoding Decoded · 2:01 · 402 views
Search Suggestions System - LeetCode 1268 - PythonAlpha-Code · 17:38 · 219 views
Search Suggestions System - Leetcode 1268 - Trie - PythonEffective Coder · 21:40 · 191 views
The problem
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 <= 10001 <= products[i].length <= 30001 <= sum(products[i].length) <= 2 * 104- All the strings of
productsare unique. products[i]consists of lowercase English letters.1 <= searchWord.length <= 1000searchWordconsists of lowercase English letters.
Approach overview
Problem Overview: You are given a list of product names and a search word. As the user types each character of the search word, return up to three lexicographically smallest products that start with the current prefix.
Approach 1: Sorting and Linear Prefix Filtering (Time: O(n log n + m * n), Space: O(1) extra)
Start by sorting the product list lexicographically using sorting. For every prefix of the search word, iterate through the sorted list and collect the first three products that start with that prefix. Because the array is sorted, the first matches you encounter are already the smallest in lexicographical order. The key operation is repeated prefix comparison using string.startswith() or substring checks. This approach is easy to implement and works well when the product list is small, but scanning the full list for every prefix leads to O(m * n) checks where m is the search word length.
Approach 2: Trie Data Structure (Time: O(n * k + m * k), Space: O(n * k))
A more scalable solution uses a Trie to store product names character by character. Each node represents a prefix and stores up to three lexicographically smallest product suggestions that share that prefix. Insert every product into the Trie while maintaining a sorted list of at most three suggestions at each node. When processing the search word, traverse the Trie one character at a time and read the stored suggestions directly from the current node. This avoids scanning the entire product list repeatedly and turns the search process into simple prefix traversal.
The Trie approach leverages prefix sharing between strings, which is exactly what the problem models. It also aligns with typical autocomplete system design. Operations mainly involve character traversal and prefix lookup within the Trie, a common pattern in string and search problems.
Recommended for interviews: The Trie solution is usually what interviewers expect because it models a real-world autocomplete system and achieves predictable performance. The sorting approach still demonstrates good understanding of lexicographical ordering and prefix filtering, so it is a solid starting point during discussion before moving to the optimized Trie-based design.
Approach 1: Sorting and Linear Search Approach
This approach involves sorting the products array first and then iteratively constructing prefixes from the searchWord. For each prefix, use a simple linear search over the sorted products array to find matches. By keeping the products sorted, it ensures that we can easily pick the smallest lexicographical options.
After sorting, for every prefix of the searchWord, we traverse the sorted products list, check if the product starts with the current prefix, and collect up to three matches.
def suggestedProducts(products, searchWord):
products.sort()
result = []
prefix = ''
for char in searchWord:
prefix += char
matches = [product for product in products if product.startswith(prefix)]
result.append(matches[:3])
return result
# Example usage:
products = ["mobile","mouse","moneypot","monitor","mousepad"]
searchWord = "mouse"
print(suggestedProducts(products, searchWord))import java.util.*;
public class SearchSuggestions {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<List<String>> result = new ArrayList<>();
String prefix = "";
for (char c : searchWord.toCharArray()) {
prefix += c;
List<String> matches = new ArrayList<>();
for (String product : products) {
if (product.startsWith(prefix)) {
matches.add(product);
if (matches.size() == 3) break;
}
}
result.add(matches);
}
return result;
}
public static void main(String[] args) {
String[] products = {"mobile","mouse","moneypot","monitor","mousepad"};
String searchWord = "mouse";
SearchSuggestions ss = new SearchSuggestions();
System.out.println(ss.suggestedProducts(products, searchWord));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
vector<vector<string>> result;
string prefix;
for (char c : searchWord) {
prefix += c;
vector<string> matches;
for (string &product : products) {
if (product.compare(0, prefix.size(), prefix) == 0) {
matches.push_back(product);
if (matches.size() == 3) break;
}
}
result.push_back(matches);
}
return result;
}
int main() {
vector<string> products = {"mobile","mouse","moneypot","monitor","mousepad"};
string searchWord = "mouse";
vector<vector<string>> result = suggestedProducts(products, searchWord);
for (auto &list : result) {
for (auto &prod : list) {
cout << prod << " ";
}
cout << endl;
}
return 0;
}function suggestedProducts(products, searchWord) {
products.sort();
let result = [];
let prefix = '';
for (let char of searchWord) {
prefix += char;
let matches = products.filter(product => product.startsWith(prefix)).slice(0, 3);
result.push(matches);
}
return result;
}
// Example usage:
const products = ["mobile","mouse","moneypot","monitor","mousepad"];
const searchWord = "mouse";
console.log(suggestedProducts(products, searchWord));using System;
using System.Collections.Generic;
class SearchSuggestions {
public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
Array.Sort(products);
List<IList<string>> result = new List<IList<string>>();
string prefix = string.Empty;
foreach (char c in searchWord) {
prefix += c;
List<string> matches = new List<string>();
foreach (string product in products) {
if (product.StartsWith(prefix)) {
matches.Add(product);
if (matches.Count == 3) break;
}
}
result.Add(matches);
}
return result;
}
static void Main() {
string[] products = {"mobile","mouse","moneypot","monitor","mousepad"};
string searchWord = "mouse";
SearchSuggestions ss = new SearchSuggestions();
var result = ss.SuggestedProducts(products, searchWord);
foreach (var list in result) {
Console.WriteLine(string.Join(" ", list));
}
}
}This Python code starts by sorting the list of products. As we iterate through each character of the searchWord, it builds the prefix and filters products that start with the current prefix. We then select the first three such products.
Time Complexity: O(n log n) due to sorting, where n is the length of products. Each prefix search is O(n), leading to an overall complexity of O(n log n + m * n), where m is the length of searchWord.
Space Complexity: O(1) additional space is needed outside the result storage, although storing results may take O(m * 3) space.
Approach 2: Trie Data Structure Approach
This approach aims at using a Trie to efficiently handle prefix matching. With a Trie, we insert all product names into the Trie. As each character is typed in the searchWord, we traverse the Trie to check for the top three lexicographical matches.
Using a Trie allows us to handle the prefix matching efficiently by navigating through the structure step by step according to the current prefix.
class TrieNode:
def __init__(self):
self.children = {}
self.suggestions = []
class Solution:
def insert(self, word, root):
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
if len(node.suggestions) < 3:
node.suggestions.append(word)
def suggestedProducts(self, products, searchWord):
root = TrieNode()
for product in sorted(products):
self.insert(product, root)
result, node = [], root
for char in searchWord:
if node:
node = node.children.get(char)
result.append(node.suggestions if node else [])
return result
# Example usage:
products = ["mobile","mouse","moneypot","monitor","mousepad"]
searchWord = "mouse"
solution = Solution()
print(solution.suggestedProducts(products, searchWord))import java.util.*;
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
List<String> suggestions = new ArrayList<>();
}
class Solution {
public void insert(String product, TrieNode node) {
for (char c : product.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
if (node.suggestions.size() < 3) {
node.suggestions.add(product);
}
}
}
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
TrieNode root = new TrieNode();
for (String product : products) {
insert(product, root);
}
List<List<String>> result = new ArrayList<>();
TrieNode node = root;
for (char c : searchWord.toCharArray()) {
node = node != null ? node.children.get(c) : null;
result.add(node != null ? node.suggestions : new ArrayList<>());
}
return result;
}
public static void main(String[] args) {
String[] products = {"mobile","mouse","moneypot","monitor","mousepad"};
String searchWord = "mouse";
Solution solution = new Solution();
System.out.println(solution.suggestedProducts(products, searchWord));
}
}#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct TrieNode {
map<char, TrieNode*> children;
vector<string> suggestions;
};
class Solution {
public:
void insert(string product, TrieNode* node) {
for (char c : product) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
if (node->suggestions.size() < 3) {
node->suggestions.push_back(product);
}
}
}
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
TrieNode* root = new TrieNode();
for (string& product : products) {
insert(product, root);
}
vector<vector<string>> result;
TrieNode* node = root;
for (char c : searchWord) {
if (node) {
node = node->children.count(c) ? node->children[c] : nullptr;
}
result.push_back(node ? node->suggestions : vector<string>());
}
return result;
}
};
int main() {
vector<string> products = {"mobile","mouse","moneypot","monitor","mousepad"};
string searchWord = "mouse";
Solution solution;
vector<vector<string>> result = solution.suggestedProducts(products, searchWord);
for (auto &list : result) {
for (auto &prod : list) {
cout << prod << " ";
}
cout << endl;
}
return 0;
}class TrieNode {
constructor() {
this.children = {};
this.suggestions = [];
}
}
function insertProduct(product, root) {
let node = root;
for (let char of product) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
if (node.suggestions.length < 3) {
node.suggestions.push(product);
}
}
}
function suggestedProducts(products, searchWord) {
products.sort();
let root = new TrieNode();
for (let product of products) {
insertProduct(product, root);
}
let result = [];
let node = root;
for (let char of searchWord) {
node = node ? node.children[char] : null;
result.push(node ? node.suggestions : []);
}
return result;
}
// Example usage:
const products = ["mobile","mouse","moneypot","monitor","mousepad"];
const searchWord = "mouse";
console.log(suggestedProducts(products, searchWord));using System;
using System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
public List<string> Suggestions = new List<string>();
}
class Solution {
public void Insert(string product, TrieNode node) {
foreach (char c in product) {
if (!node.Children.ContainsKey(c)) {
node.Children[c] = new TrieNode();
}
node = node.Children[c];
if (node.Suggestions.Count < 3) {
node.Suggestions.Add(product);
}
}
}
public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
Array.Sort(products);
TrieNode root = new TrieNode();
foreach (string product in products) {
Insert(product, root);
}
List<IList<string>> result = new List<IList<string>>();
TrieNode node = root;
foreach (char c in searchWord) {
if (node != null) {
node = node.Children.ContainsKey(c) ? node.Children[c] : null;
}
result.Add(node != null ? new List<string>(node.Suggestions) : new List<string>());
}
return result;
}
static void Main() {
string[] products = {"mobile","mouse","moneypot","monitor","mousepad"};
string searchWord = "mouse";
Solution solution = new Solution();
var result = solution.SuggestedProducts(products, searchWord);
foreach (var list in result) {
Console.WriteLine(string.Join(" ", list));
}
}
}This Python code uses a Trie structure. We create nodes for each character and keep track of the top three suggestions within the TrieNode. As searchWord is typed, we navigate the Trie and retrieve suggestions.
Time Complexity: O(n m) to insert all products (where n is number of products and m is max product length), and O(k) to search for each prefix (where k is the length of searchWord).
Space Complexity: O(n m) for the Trie storage, since we store each character of every word.
Approach 3: Sorting + Trie
The problem requires that after each letter of the input searchWord, recommend up to three products from the products array that have the same prefix as searchWord. If there are more than three products with the same prefix that can be recommended, return the three with the smallest lexicographic order.
To find products with the same prefix, we can use a trie; to return the three products with the smallest lexicographic order, we can first sort the products array, and then store the indices of the sorted array in the trie.
Each node of the trie maintains the following information:
children: This is an array of length26, used to store the child nodes of the current node.children[i]represents the node whose character isi + 'a'among the child nodes of the current node.v: This is an array, used to store the indices of the characters in theproductsarray among the child nodes of the current node, storing up to three indices.
During the search, we start from the root node of the trie, find the index array corresponding to each prefix, and store it in the result array. Finally, we only need to map each index in the index array to the products array.
The time complexity is O(L times log n + m), and the space complexity is O(L). Where L is the sum of the lengths of all strings in the products array, and n and m are the lengths of the products array and searchWord, respectively.
type Trie struct {
children [26]*Trie
v []int
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(w string, i int) {
node := this
for _, c := range w {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
if len(node.v) < 3 {
node.v = append(node.v, i)
}
}
}
func (this *Trie) search(w string) [][]int {
node := this
n := len(w)
ans := make([][]int, n)
for i, c := range w {
c -= 'a'
if node.children[c] == nil {
break
}
node = node.children[c]
ans[i] = node.v
}
return ans
}
func suggestedProducts(products []string, searchWord string) (ans [][]string) {
sort.Strings(products)
trie := newTrie()
for i, w := range products {
trie.insert(w, i)
}
for _, v := range trie.search(searchWord) {
t := []string{}
for _, i := range v {
t = append(t, products[i])
}
ans = append(ans, t)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Linear Search Approach | Time Complexity: O(n log n) due to sorting, where n is the length of products. Each prefix search is O(n), leading to an overall complexity of O(n log n + m * n), where m is the length of searchWord. Space Complexity: O(1) additional space is needed outside the result storage, although storing results may take O(m * 3) space. |
| Trie Data Structure Approach | Time Complexity: O(n m) to insert all products (where n is number of products and m is max product length), and O(k) to search for each prefix (where k is the length of searchWord). Space Complexity: O(n m) for the Trie storage, since we store each character of every word. |
| Sorting + Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Linear Prefix Filtering | O(n log n + m * n) | O(1) | Simple implementation when the product list is small or constraints are moderate |
| Trie Data Structure | O(n * k + m * k) | O(n * k) | Best for large datasets or autocomplete-style systems requiring fast prefix lookups |
Frequently asked questions
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.