Search Suggestions System
MedPrompt
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.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach simulates the process directly. For each character typed, it forms the current prefix. It then iterates through the entire list of products, collecting all products that start with this prefix. Finally, it sorts the collected matches and picks the top three.
Algorithm
- Initialize an empty list of lists
result. - Initialize an empty string
prefix. - Iterate through each character
cofsearchWord:- Append
ctoprefix. - Create an empty list
suggestions. - Iterate through each
productin theproductsarray:- If
productstarts withprefix, addproducttosuggestions.
- If
- Sort
suggestionslexicographically. - Create a new list
currentResult. - Add the first
min(3, suggestions.size())elements fromsuggestionstocurrentResult. - Add
currentResulttoresult.
- Append
- Return
result.
Walkthrough
We iterate from the first character of searchWord up to its full length.
In each iteration i, we consider the prefix p = searchWord.substring(0, i+1).
We create a temporary list, matches.
We loop through every product in the products array.
For each product, we check if it startsWith(p). If it does, we add it to matches.
After checking all products, we sort the matches list lexicographically.
We then take the first 3 elements from the sorted matches list (or all of them if there are fewer than 3) and add this sublist to our final result.
This process is repeated for all prefixes of searchWord.
class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { List<List<String>> result = new ArrayList<>(); StringBuilder prefix = new StringBuilder(); for (char c : searchWord.toCharArray()) { prefix.append(c); List<String> matches = new ArrayList<>(); for (String product : products) { if (product.startsWith(prefix.toString())) { matches.add(product); } } Collections.sort(matches); List<String> suggestions = new ArrayList<>(); for (int i = 0; i < Math.min(3, matches.size()); i++) { suggestions.add(matches.get(i)); } result.add(suggestions); } return result; }}Complexity
Time
O(M * (N*L + N log N * L)), where `M` is the length of `searchWord`, `N` is the number of products, and `L` is the maximum length of a product. For each of the `M` prefixes, we iterate through `N` products (`O(N)`), each `startsWith` check takes up to `O(L)` time, and sorting `N` products takes `O(N log N * L)`. This is highly inefficient.
Space
O(N * L), where N is the number of products and L is their maximum length. This space is required to store the matching products for each prefix before sorting and trimming.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very slow, especially for long search words and large product lists.
It recomputes and re-sorts for every single character typed, leading to a lot of redundant work.
This approach improves upon the brute-force method by pre-sorting the products array. Once sorted, all products with a common prefix will be grouped together. For each prefix, we can use binary search to quickly find the starting point of this group.
Algorithm
- Sort the
productsarray lexicographically usingArrays.sort(products). - Initialize an empty list of lists
result. - Build a
prefixstring character by character fromsearchWord. - For each
prefix:- Use binary search to find the index
startof the first word inproductsthat is greater than or equal to theprefix. - Initialize an empty list
suggestions. - Iterate from
startfor up to 3 elements or until the end of the array. - If
products[i]starts with theprefix, add it tosuggestions. - Add the
suggestionslist to theresult.
- Use binary search to find the index
- Return
result.
Walkthrough
First, we sort the products array lexicographically. This is a one-time operation.
We then iterate through each character of searchWord to form prefixes, one by one.
For each prefix, we use binary search (like a custom lower_bound function) to find the insertion point of this prefix in the sorted products array. This index, let's call it start, is where the block of matching products begins.
Starting from start, we iterate through the products array. We check the next few products to see if they actually start with the current prefix.
We collect up to three such matching products. Since the array is sorted, these will be the lexicographically smallest ones.
We can stop checking as soon as we find a product that doesn't start with the prefix, or once we have collected three suggestions.
class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); List<List<String>> result = new ArrayList<>(); StringBuilder prefix = new StringBuilder(); for (char c : searchWord.toCharArray()) { prefix.append(c); int start = findLowerBound(products, prefix.toString()); List<String> suggestions = new ArrayList<>(); for (int i = start; i < Math.min(start + 3, products.length); i++) { if (products[i].startsWith(prefix.toString())) { suggestions.add(products[i]); } } result.add(suggestions); } return result; } // Custom binary search to find the first element >= target private int findLowerBound(String[] products, String target) { int low = 0, high = products.length; int ans = products.length; while (low < high) { int mid = low + (high - low) / 2; if (products[mid].compareTo(target) >= 0) { ans = mid; high = mid; } else { low = mid + 1; } } return ans; }}Complexity
Time
O(N log N * L + M * L * log N). Sorting takes `O(N log N * L)`. For each of the `M` prefixes, binary search takes `O(log N)` comparisons, and each string comparison takes up to `O(L)` time.
Space
O(L) for storing the prefix, plus the space for sorting (typically `O(log N)` or `O(N)` depending on implementation) and the output list.
Trade-offs
Pros
Much faster than brute force due to pre-sorting and efficient searching with binary search.
Cons
Performs a separate binary search for each prefix, which involves some redundant work.
A Trie is a tree-like data structure that is ideal for prefix-based searches. We can build a Trie from the products list and store suggestions at each node. This allows for very fast lookups once the Trie is constructed.
Algorithm
- Sort the
productsarray lexicographically. - Create a
Triewith a rootTrieNode. Each node should contain children pointers and a list for suggestions. - For each
productin the sortedproductsarray:- Insert the
productinto the Trie. At eachTrieNodealong the insertion path, ifnode.suggestions.size() < 3, add theproducttonode.suggestions.
- Insert the
- Initialize an empty list of lists
result. - Traverse the Trie using characters from
searchWord, starting from the root. - For each character, move to the corresponding child node.
- If the path exists, add the suggestions from the current node to the
result. Otherwise, add an empty list. - Continue until all characters of
searchWordare processed. - Return
result.
Walkthrough
To optimize, we first sort the products array lexicographically.
We define a TrieNode class, where each node contains an array of children (for each letter 'a'-'z') and a list to store suggestions.
We build the Trie by inserting every product from the sorted list. As we traverse the Trie for a product, we add that product to the suggestion list of each node on the path, but only if the list has fewer than 3 items. Since we insert products in lexicographical order, the first three products encountered for any prefix path will be the smallest ones.
After building the Trie, we search for suggestions. We traverse the Trie character by character according to searchWord.
For each character, we move to the corresponding child node. We then add the suggestion list from that node to our result.
If at any point a character does not have a corresponding child node, it means no products match from that point on. We then fill the rest of the results with empty lists.
class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; List<String> suggestions = new ArrayList<>(); } public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); TrieNode root = new TrieNode(); // Build Trie for (String p : products) { TrieNode node = root; for (char c : p.toCharArray()) { if (node.children[c - 'a'] == null) { node.children[c - 'a'] = new TrieNode(); } node = node.children[c - 'a']; if (node.suggestions.size() < 3) { node.suggestions.add(p); } } } // Search List<List<String>> result = new ArrayList<>(); TrieNode node = root; for (char c : searchWord.toCharArray()) { if (node != null) { node = node.children[c - 'a']; } if (node == null) { result.add(new ArrayList<>()); } else { result.add(node.suggestions); } } return result; }}Complexity
Time
O(N log N * L + S), where `S` is the total number of characters in all products. Sorting takes `O(N log N * L)`. Building the Trie takes `O(S)`. Searching takes `O(M)`. The overall complexity is dominated by the preprocessing steps.
Space
O(S), where `S` is the total number of characters in all products. The number of nodes in the Trie is at most `S`. Each node stores pointers to children and a small list of suggestions (pointers to strings), so the space is proportional to `S`.
Trade-offs
Pros
Extremely fast search time (
O(M)).A good choice if the product list is static and queried many times.
Cons
Higher space complexity compared to the two-pointer approach.
The preprocessing time (sorting and building the Trie) can be significant.
This is the most efficient approach in terms of both time and space. It starts by sorting the products array. Then, instead of re-searching from scratch for each prefix, it maintains a left and right pointer to narrow down the range of matching products as the prefix gets longer.
Algorithm
- Sort the
productsarray lexicographically. - Initialize two pointers,
left = 0andright = products.length - 1. - Iterate through
searchWordwith indexi.- Get the character
c = searchWord.charAt(i). - Move
leftpointer forward whileleft <= rightandproducts[left]does not match the prefix up toi. - Move
rightpointer backward whileleft <= rightandproducts[right]does not match the prefix up toi. - The products in the range
[left, right]now match the current prefix. - Add up to the first 3 products from this range to the current list of suggestions.
- Add the suggestions to the final result list.
- Get the character
- Return the result.
Walkthrough
First, sort the products array lexicographically.
Initialize two pointers, left = 0 and right = products.length - 1. These pointers will define the window of products that are candidates for the current prefix.
Iterate through the searchWord character by character (from index i = 0 to M-1).
In each iteration, shrink the window [left, right]:
- Move
leftforward as long asproducts[left]does not match the prefix up to characteri. A product doesn't match if it's too short (length< i+1) or if the character at indexiis different from thei-th character ofsearchWord. - Similarly, move
rightbackward as long asproducts[right]does not match the prefix. After adjusting the pointers, all products betweenleftandright(inclusive) are guaranteed to have the current prefix. The first three products in this range (products[left],products[left+1], ...) are the desired suggestions. We add up to three of these to our result list for the current prefix. The number of suggestions will bemin(3, right - left + 1).
class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); List<List<String>> result = new ArrayList<>(); int left = 0; int right = products.length - 1; for (int i = 0; i < searchWord.length(); i++) { char c = searchWord.charAt(i); // Move left pointer while (left <= right && (products[left].length() <= i || products[left].charAt(i) != c)) { left++; } // Move right pointer while (left <= right && (products[right].length() <= i || products[right].charAt(i) != c)) { right--; } List<String> suggestions = new ArrayList<>(); if (left <= right) { int count = Math.min(3, right - left + 1); for (int j = 0; j < count; j++) { suggestions.add(products[left + j]); } } result.add(suggestions); } return result; }}Complexity
Time
O(N log N * L + M + N). Sorting takes `O(N log N * L)`. The two pointers `left` and `right` traverse the array at most once in total across all iterations of the main loop, which takes `O(N)` character comparisons. The outer loop runs `M` times. So the search part is `O(M + N)`. The total time is dominated by sorting.
Space
O(log N) or O(N) for the in-place sort, depending on the language's implementation. This is very space-efficient.
Trade-offs
Pros
Optimal time complexity and very low space complexity.
Generally the best all-around solution for this problem.
Cons
The initial sorting cost might be high if the number of products is very large, but it's generally necessary for finding the lexicographically smallest results efficiently.
Solutions
Solution
class Trie { Trie [] children = new Trie [ 26 ]; List < Integer > v = new ArrayList <>(); public void insert ( String w , int i ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; if ( node . v . size () < 3 ) { node . v . add ( i ); } } } public List < Integer >[] search ( String w ) { Trie node = this ; int n = w . length (); List < Integer >[] ans = new List [ n ]; Arrays . setAll ( ans , k -> new ArrayList <>()); for ( int i = 0 ; i < n ; ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { break ; } node = node . children [ idx ]; ans [ i ] = node . v ; } return ans ; } } class Solution { public List < List < String >> suggestedProducts ( String [] products , String searchWord ) { Arrays . sort ( products ); Trie trie = new Trie (); for ( int i = 0 ; i < products . length ; ++ i ) { trie . insert ( products [ i ], i ); } List < List < String >> ans = new ArrayList <>(); for ( var v : trie . search ( searchWord )) { List < String > t = new ArrayList <>(); for ( int i : v ) { t . add ( products [ i ]); } ans . add ( t ); } return ans ; } }class Trie { public: void insert ( string & w , int i ) { Trie * node = this ; for ( int j = 0 ; j < w . size (); ++ j ) { int idx = w [ j ] - 'a' ; if ( ! node -> children [ idx ]) { node -> children [ idx ] = new Trie (); } node = node -> children [ idx ]; if ( node -> v . size () < 3 ) { node -> v . push_back ( i ); } } } vector < vector < int >> search ( string & w ) { Trie * node = this ; int n = w . size (); vector < vector < int >> ans ( n ); for ( int i = 0 ; i < w . size (); ++ i ) { int idx = w [ i ] - 'a' ; if ( ! node -> children [ idx ]) { break ; } node = node -> children [ idx ]; ans [ i ] = move ( node -> v ); } return ans ; } private: vector < Trie *> children = vector < Trie *> ( 26 ); vector < int > v ; }; class Solution { public: vector < vector < string >> suggestedProducts ( vector < string >& products , string searchWord ) { sort ( products . begin (), products . end ()); Trie * trie = new Trie (); for ( int i = 0 ; i < products . size (); ++ i ) { trie -> insert ( products [ i ], i ); } vector < vector < string >> ans ; for ( auto & v : trie -> search ( searchWord )) { vector < string > t ; for ( int i : v ) { t . push_back ( products [ i ]); } ans . push_back ( move ( t )); } return ans ; } };class Trie : def __init__ ( self ): self . children : List [ Union [ Trie , None ]] = [ None ] * 26 self . v : List [ int ] = [] def insert ( self , w , i ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] if len ( node . v ) < 3 : node . v . append ( i ) def search ( self , w ): node = self ans = [[] for _ in range ( len ( w ))] for i , c in enumerate ( w ): idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : break node = node . children [ idx ] ans [ i ] = node . v return ans class Solution : def suggestedProducts ( self , products : List [ str ], searchWord : str ) -> List [ List [ str ]]: products . sort () trie = Trie () for i , w in enumerate ( products ): trie . insert ( w , i ) return [[ products [ i ] for i in v ] for v in trie . search ( searchWord )]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.