1268. Search Suggestions System

MediumTrieArrayStringBinary SearchSortingHeap (Priority Queue)
Leetcode Link

Problem Description

You need to build a product search suggestion system. Given an array of product names products and a search word searchWord, your system should suggest products as the user types each character of the search word.

The requirements are:

  • After typing each character of searchWord, suggest up to 3 products from products that start with the currently typed prefix
  • If more than 3 products match the prefix, return the 3 that come first lexicographically (alphabetically)
  • Return the suggestions as a list of lists, where each inner list contains the suggestions after typing each character

For example, if products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"] and searchWord = "mouse":

  • After typing "m": suggest ["mobile", "moneypot", "monitor"] (3 products starting with "m", sorted alphabetically)
  • After typing "mo": suggest ["mobile", "moneypot", "monitor"] (3 products starting with "mo")
  • After typing "mou": suggest ["mouse", "mousepad"] (only 2 products start with "mou")
  • After typing "mous": suggest ["mouse", "mousepad"]
  • After typing "mouse": suggest ["mouse", "mousepad"]

The solution uses a Trie data structure combined with sorting. First, the products are sorted alphabetically. Then a Trie is built where each node stores up to 3 product indices that have the corresponding prefix. When searching, for each character typed, the Trie traversal finds the matching products efficiently. The indices stored in the Trie nodes are then mapped back to the actual product names from the sorted products array.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we need to find products that share a common prefix with what's being typed, the natural data structure that comes to mind is a Trie (prefix tree). A Trie excels at prefix matching because each path from the root to a node represents a prefix, and we can efficiently traverse character by character.

However, we also need to return the lexicographically smallest products when there are more than 3 matches. Rather than sorting products at each node during search time, we can pre-sort the entire products array once. This way, when we insert products into the Trie in sorted order, the first products we encounter for any prefix are automatically the lexicographically smallest ones.

The key insight is to store indices instead of actual product names in the Trie nodes. Since we've pre-sorted the products array, if we store indices [i, j, k] where i < j < k, we know that products[i] comes before products[j] lexicographically, which comes before products[k].

By limiting each Trie node to store at most 3 indices, we automatically maintain the "top 3 lexicographically smallest" products for each prefix. As we build the Trie by inserting products in sorted order, the first 3 products that pass through any node are guaranteed to be the 3 smallest for that prefix.

During the search phase, we simply traverse the Trie following the characters of searchWord. At each step, the current node already contains the indices of up to 3 best matching products, which we can directly add to our result. If at any point a character doesn't exist in the Trie, we know there are no matching products for that prefix and all subsequent prefixes, so we can stop early.

Learn more about Trie, Binary Search, Sorting and Heap (Priority Queue) patterns.

Solution Implementation

1from typing import List, Optional 2 3class Trie: 4 def __init__(self): 5 # Array to store 26 possible child nodes (one for each lowercase letter) 6 self.children: List[Optional['Trie']] = [None] * 26 7 # Store indices of up to 3 products that have this prefix 8 self.product_indices: List[int] = [] 9 10 def insert(self, word: str, product_index: int) -> None: 11 """Insert a word into the trie with its product index.""" 12 current_node = self 13 14 for char in word: 15 # Calculate the index for this character (0-25) 16 char_index = ord(char) - ord('a') 17 18 # Create a new node if it doesn't exist 19 if current_node.children[char_index] is None: 20 current_node.children[char_index] = Trie() 21 22 # Move to the child node 23 current_node = current_node.children[char_index] 24 25 # Store up to 3 product indices at each node 26 if len(current_node.product_indices) < 3: 27 current_node.product_indices.append(product_index) 28 29 def search(self, word: str) -> List[List[int]]: 30 """Search for product suggestions for each prefix of the given word.""" 31 current_node = self 32 # Initialize result list with empty lists for each character position 33 suggestions = [[] for _ in range(len(word))] 34 35 for position, char in enumerate(word): 36 # Calculate the index for this character 37 char_index = ord(char) - ord('a') 38 39 # If no child exists for this character, no more matches possible 40 if current_node.children[char_index] is None: 41 break 42 43 # Move to the child node 44 current_node = current_node.children[char_index] 45 # Store the product indices for this prefix 46 suggestions[position] = current_node.product_indices 47 48 return suggestions 49 50 51class Solution: 52 def suggestedProducts( 53 self, products: List[str], searchWord: str 54 ) -> List[List[str]]: 55 """ 56 Return suggested products for each prefix of searchWord. 57 For each prefix, return up to 3 lexicographically smallest products. 58 """ 59 # Sort products lexicographically 60 products.sort() 61 62 # Build the trie with all products 63 trie = Trie() 64 for index, product in enumerate(products): 65 trie.insert(product, index) 66 67 # Get suggestions for each prefix and convert indices to product names 68 suggestion_indices = trie.search(searchWord) 69 return [[products[index] for index in indices] for indices in suggestion_indices] 70
1/** 2 * Trie data structure for efficient prefix-based search 3 * Each node stores up to 3 product indices for suggestions 4 */ 5class Trie { 6 // Array of child nodes for each lowercase letter (a-z) 7 Trie[] children = new Trie[26]; 8 // List to store indices of products (max 3) that have this prefix 9 List<Integer> productIndices = new ArrayList<>(); 10 11 /** 12 * Inserts a word into the trie with its corresponding product index 13 * @param word The product name to insert 14 * @param index The index of the product in the sorted products array 15 */ 16 public void insert(String word, int index) { 17 Trie currentNode = this; 18 19 // Traverse through each character in the word 20 for (int i = 0; i < word.length(); i++) { 21 // Calculate the index for the character (0-25 for a-z) 22 int charIndex = word.charAt(i) - 'a'; 23 24 // Create a new node if it doesn't exist 25 if (currentNode.children[charIndex] == null) { 26 currentNode.children[charIndex] = new Trie(); 27 } 28 29 // Move to the child node 30 currentNode = currentNode.children[charIndex]; 31 32 // Store the product index (maximum 3 products per node) 33 if (currentNode.productIndices.size() < 3) { 34 currentNode.productIndices.add(index); 35 } 36 } 37 } 38 39 /** 40 * Searches for product suggestions for each prefix of the search word 41 * @param searchWord The word to search for 42 * @return Array of lists containing product indices for each prefix 43 */ 44 public List<Integer>[] search(String searchWord) { 45 Trie currentNode = this; 46 int wordLength = searchWord.length(); 47 48 // Initialize result array with empty lists for each character position 49 List<Integer>[] results = new List[wordLength]; 50 Arrays.setAll(results, i -> new ArrayList<>()); 51 52 // Traverse through each character of the search word 53 for (int i = 0; i < wordLength; i++) { 54 int charIndex = searchWord.charAt(i) - 'a'; 55 56 // If no matching child exists, stop searching 57 if (currentNode.children[charIndex] == null) { 58 break; 59 } 60 61 // Move to the child node and store its product indices 62 currentNode = currentNode.children[charIndex]; 63 results[i] = currentNode.productIndices; 64 } 65 66 return results; 67 } 68} 69 70/** 71 * Solution class for the product suggestion system problem 72 */ 73class Solution { 74 /** 75 * Returns suggested products for each prefix of the search word 76 * @param products Array of product names 77 * @param searchWord The word to search for 78 * @return List of lists containing suggested product names for each prefix 79 */ 80 public List<List<String>> suggestedProducts(String[] products, String searchWord) { 81 // Sort products lexicographically to ensure suggestions are in order 82 Arrays.sort(products); 83 84 // Build the trie with all products 85 Trie trie = new Trie(); 86 for (int i = 0; i < products.length; i++) { 87 trie.insert(products[i], i); 88 } 89 90 // Get product indices for each prefix of the search word 91 List<Integer>[] productIndicesArray = trie.search(searchWord); 92 93 // Convert indices to actual product names 94 List<List<String>> suggestions = new ArrayList<>(); 95 for (List<Integer> indices : productIndicesArray) { 96 List<String> productNames = new ArrayList<>(); 97 for (int productIndex : indices) { 98 productNames.add(products[productIndex]); 99 } 100 suggestions.add(productNames); 101 } 102 103 return suggestions; 104 } 105} 106
1class Trie { 2public: 3 /** 4 * Insert a word into the trie with its index in the products array 5 * At each node, store up to 3 product indices (lexicographically smallest) 6 * @param word: the product word to insert 7 * @param productIndex: the index of this product in the sorted products array 8 */ 9 void insert(string& word, int productIndex) { 10 Trie* currentNode = this; 11 12 // Traverse each character in the word 13 for (int charPos = 0; charPos < word.size(); ++charPos) { 14 int charIndex = word[charPos] - 'a'; 15 16 // Create new node if path doesn't exist 17 if (!currentNode->children[charIndex]) { 18 currentNode->children[charIndex] = new Trie(); 19 } 20 21 // Move to next node 22 currentNode = currentNode->children[charIndex]; 23 24 // Store up to 3 product indices at this node 25 if (currentNode->productIndices.size() < 3) { 26 currentNode->productIndices.push_back(productIndex); 27 } 28 } 29 } 30 31 /** 32 * Search for suggestions for each prefix of the search word 33 * @param searchWord: the word to search for 34 * @return: a 2D vector where ans[i] contains product indices for prefix searchWord[0..i] 35 */ 36 vector<vector<int>> search(string& searchWord) { 37 Trie* currentNode = this; 38 int wordLength = searchWord.size(); 39 vector<vector<int>> suggestions(wordLength); 40 41 // For each character in searchWord, find matching products 42 for (int charPos = 0; charPos < searchWord.size(); ++charPos) { 43 int charIndex = searchWord[charPos] - 'a'; 44 45 // If no matching path exists, remaining suggestions will be empty 46 if (!currentNode->children[charIndex]) { 47 break; 48 } 49 50 // Move to next node and get its stored product indices 51 currentNode = currentNode->children[charIndex]; 52 suggestions[charPos] = move(currentNode->productIndices); 53 } 54 55 return suggestions; 56 } 57 58private: 59 // Array of 26 pointers for each lowercase letter 60 vector<Trie*> children = vector<Trie*>(26); 61 62 // Stores up to 3 product indices at this node 63 vector<int> productIndices; 64}; 65 66class Solution { 67public: 68 /** 69 * Find suggested products for each prefix of searchWord 70 * Returns at most 3 lexicographically smallest products for each prefix 71 * @param products: list of available products 72 * @param searchWord: the word being typed/searched 73 * @return: suggestions for each prefix of searchWord 74 */ 75 vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) { 76 // Sort products lexicographically 77 sort(products.begin(), products.end()); 78 79 // Build trie with all products 80 Trie* trie = new Trie(); 81 for (int i = 0; i < products.size(); ++i) { 82 trie->insert(products[i], i); 83 } 84 85 // Get suggestions for each prefix of searchWord 86 vector<vector<string>> result; 87 vector<vector<int>> suggestionIndices = trie->search(searchWord); 88 89 // Convert product indices back to product names 90 for (auto& indices : suggestionIndices) { 91 vector<string> suggestions; 92 for (int index : indices) { 93 suggestions.push_back(products[index]); 94 } 95 result.push_back(move(suggestions)); 96 } 97 98 return result; 99 } 100}; 101
1/** 2 * Trie node structure for storing product suggestions 3 */ 4interface TrieNode { 5 // Array of 26 children nodes for each lowercase letter 6 children: (TrieNode | null)[]; 7 // Stores up to 3 product indices at this node 8 productIndices: number[]; 9} 10 11/** 12 * Creates a new trie node 13 * @returns A new trie node with empty children and product indices 14 */ 15function createTrieNode(): TrieNode { 16 return { 17 children: new Array(26).fill(null), 18 productIndices: [] 19 }; 20} 21 22/** 23 * Insert a word into the trie with its index in the products array 24 * At each node, store up to 3 product indices (lexicographically smallest) 25 * @param root - The root node of the trie 26 * @param word - The product word to insert 27 * @param productIndex - The index of this product in the sorted products array 28 */ 29function insert(root: TrieNode, word: string, productIndex: number): void { 30 let currentNode = root; 31 32 // Traverse each character in the word 33 for (let charPos = 0; charPos < word.length; charPos++) { 34 const charIndex = word.charCodeAt(charPos) - 'a'.charCodeAt(0); 35 36 // Create new node if path doesn't exist 37 if (!currentNode.children[charIndex]) { 38 currentNode.children[charIndex] = createTrieNode(); 39 } 40 41 // Move to next node 42 currentNode = currentNode.children[charIndex]!; 43 44 // Store up to 3 product indices at this node 45 if (currentNode.productIndices.length < 3) { 46 currentNode.productIndices.push(productIndex); 47 } 48 } 49} 50 51/** 52 * Search for suggestions for each prefix of the search word 53 * @param root - The root node of the trie 54 * @param searchWord - The word to search for 55 * @returns A 2D array where result[i] contains product indices for prefix searchWord[0..i] 56 */ 57function search(root: TrieNode, searchWord: string): number[][] { 58 let currentNode = root; 59 const wordLength = searchWord.length; 60 const suggestions: number[][] = new Array(wordLength).fill(null).map(() => []); 61 62 // For each character in searchWord, find matching products 63 for (let charPos = 0; charPos < searchWord.length; charPos++) { 64 const charIndex = searchWord.charCodeAt(charPos) - 'a'.charCodeAt(0); 65 66 // If no matching path exists, remaining suggestions will be empty 67 if (!currentNode.children[charIndex]) { 68 break; 69 } 70 71 // Move to next node and get its stored product indices 72 currentNode = currentNode.children[charIndex]!; 73 suggestions[charPos] = [...currentNode.productIndices]; 74 } 75 76 return suggestions; 77} 78 79/** 80 * Find suggested products for each prefix of searchWord 81 * Returns at most 3 lexicographically smallest products for each prefix 82 * @param products - List of available products 83 * @param searchWord - The word being typed/searched 84 * @returns Suggestions for each prefix of searchWord 85 */ 86function suggestedProducts(products: string[], searchWord: string): string[][] { 87 // Sort products lexicographically 88 const sortedProducts = [...products].sort(); 89 90 // Build trie with all products 91 const trieRoot = createTrieNode(); 92 for (let i = 0; i < sortedProducts.length; i++) { 93 insert(trieRoot, sortedProducts[i], i); 94 } 95 96 // Get suggestions for each prefix of searchWord 97 const result: string[][] = []; 98 const suggestionIndices = search(trieRoot, searchWord); 99 100 // Convert product indices back to product names 101 for (const indices of suggestionIndices) { 102 const suggestions: string[] = []; 103 for (const index of indices) { 104 suggestions.push(sortedProducts[index]); 105 } 106 result.push(suggestions); 107 } 108 109 return result; 110} 111

Solution Approach

The implementation consists of two main components: a Trie data structure and the main solution class.

Trie Implementation:

Each Trie node contains:

  • children: An array of size 26 (for lowercase letters a-z), where children[i] points to the child node for character 'a' + i. Initially all are None.
  • v: A list that stores up to 3 product indices that have the prefix represented by the path to this node.

The insert method adds a word to the Trie:

def insert(self, w, i):  node = self  for c in w:  idx = ord(c) - ord('a') # Convert character to index (0-25)  if node.children[idx] is None:  node.children[idx] = Trie() # Create new node if needed  node = node.children[idx]  if len(node.v) < 3:  node.v.append(i) # Store product index (max 3)

For each character in the word, we calculate its index (0-25), create a child node if it doesn't exist, move to that child, and add the product index if we haven't stored 3 products yet.

The search method finds suggestions for each prefix:

def search(self, w):  node = self  ans = [[] for _ in range(len(w))] # Initialize result for each character  for i, c in enumerate(w):  idx = ord(c) - ord('a')  if node.children[idx] is None:  break # No products with this prefix  node = node.children[idx]  ans[i] = node.v # Get stored indices for this prefix  return ans

We traverse the Trie following the search word. If we can't find a character, we stop (remaining results stay empty). Otherwise, we collect the stored indices at each node.

Main Solution:

  1. Sort the products: products.sort() ensures lexicographic ordering.

  2. Build the Trie: Insert each product with its index in the sorted array:

trie = Trie() for i, w in enumerate(products):  trie.insert(w, i)
  1. Search and map indices to products:
return [[products[i] for i in v] for v in [trie](/problems/trie_intro).search(searchWord)]

The search returns indices for each prefix, which we map back to actual product names.

Time Complexity:

  • Building Trie: O(N * M) where N is the number of products and M is the average length of products
  • Sorting: O(N * log N * M) for comparing strings
  • Searching: O(L) where L is the length of searchWord
  • Total: O(N * log N * M + N * M + L)

Space Complexity: O(N * M) for storing the Trie structure.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with products = ["apple", "apricot", "application"] and searchWord = "app".

Step 1: Sort the products alphabetically After sorting: ["apple", "application", "apricot"]

  • Indices: apple → 0, application → 1, apricot → 2

Step 2: Build the Trie

Insert "apple" (index 0):

root  └─ a: [0]  └─ p: [0]  └─ p: [0]  └─ l: [0]  └─ e: [0]

Insert "application" (index 1):

root  └─ a: [0,1]  └─ p: [0,1]  └─ p: [0,1]  └─ l: [0,1]  ├─ e: [0]  └─ i: [1]  └─ c: [1]  └─ a: [1]  └─ t: [1]  └─ i: [1]  └─ o: [1]  └─ n: [1]

Insert "apricot" (index 2):

root  └─ a: [0,1,2]  └─ p: [0,1,2]  ├─ p: [0,1]  │ └─ l: [0,1]  │ ├─ e: [0]  │ └─ i: [1]...  └─ r: [2]  └─ i: [2]  └─ c: [2]  └─ o: [2]  └─ t: [2]

Step 3: Search for "app"

  • Type 'a': Traverse to node 'a', which stores [0,1,2]

    • Map to products: ["apple", "application", "apricot"]

  • Type 'p' (prefix "ap"): Traverse to node 'p' under 'a', which stores [0,1,2]

    • Map to products: ["apple", "application", "apricot"]

  • Type 'p' (prefix "app"): Traverse to node 'p' under 'ap', which stores [0,1]

    • Map to products: ["apple", "application"]

Final Result: [["apple", "application", "apricot"], ["apple", "application", "apricot"], ["apple", "application"]]

Each inner list represents the suggestions after typing each character. Notice how:

  • The Trie stores at most 3 indices per node
  • Products are suggested in lexicographic order because we sorted first
  • Only products with the exact prefix are returned (e.g., "apricot" doesn't match "app")

Time and Space Complexity

Time Complexity: O(L × log n + m)

  • Sorting the products array takes O(n × log n × k) where k is the average length of product strings. This can be simplified to O(L × log n) where L is the total length of all product strings.
  • Building the Trie requires iterating through all products and inserting each character, which takes O(L) time total.
  • Each node stores at most 3 indices in the v list, and appending to this list is O(1).
  • Searching in the Trie for the searchWord takes O(m) where m is the length of searchWord.
  • Converting the indices back to product strings takes O(m) since each prefix can have at most 3 suggestions.
  • Overall time complexity: O(L × log n + L + m) = O(L × log n + m) (since L × log n dominates L).

Space Complexity: O(L)

  • The Trie structure can have at most O(L) nodes in the worst case, where each character of every product creates a new node.
  • Each node contains an array of 26 pointers to children and a list v that stores at most 3 indices.
  • The space for storing indices is O(L) in total across all nodes (at most 3 indices per node, and O(L) nodes).
  • The result list for search operation uses O(m) space temporarily.
  • Overall space complexity: O(L).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Empty Prefixes When No Matches Exist

A common mistake is not properly handling the case when a character in the search word doesn't exist in the Trie. When we encounter a character that has no corresponding child node, we break out of the loop, but the remaining positions in the result list stay as empty lists (which is correct). However, developers often make mistakes by:

  • Trying to continue traversal after hitting a None child
  • Not initializing the result list properly with empty lists
  • Attempting to access node.product_indices when node is None

Incorrect Implementation:

def search(self, word: str) -> List[List[int]]:  current_node = self  suggestions = [] # Wrong: not pre-initialized with empty lists   for position, char in enumerate(word):  char_index = ord(char) - ord('a')  current_node = current_node.children[char_index] # Dangerous: might be None  suggestions.append(current_node.product_indices) # Will crash if current_node is None   return suggestions

Correct Implementation:

def search(self, word: str) -> List[List[int]]:  current_node = self  suggestions = [[] for _ in range(len(word))] # Pre-initialize with empty lists   for position, char in enumerate(word):  char_index = ord(char) - ord('a')  if current_node.children[char_index] is None:  break # Stop searching, remaining positions stay empty  current_node = current_node.children[char_index]  suggestions[position] = current_node.product_indices   return suggestions

2. Adding Product Indices Without Checking the 3-Product Limit

Another pitfall is forgetting to limit the number of products stored at each Trie node to 3. Without this check, all matching products would be stored, defeating the purpose of the optimization and potentially returning more than 3 suggestions.

Incorrect Implementation:

def insert(self, word: str, product_index: int) -> None:  current_node = self   for char in word:  char_index = ord(char) - ord('a')  if current_node.children[char_index] is None:  current_node.children[char_index] = Trie()  current_node = current_node.children[char_index]  current_node.product_indices.append(product_index) # Wrong: no limit check

Correct Implementation:

def insert(self, word: str, product_index: int) -> None:  current_node = self   for char in word:  char_index = ord(char) - ord('a')  if current_node.children[char_index] is None:  current_node.children[char_index] = Trie()  current_node = current_node.children[char_index]  if len(current_node.product_indices) < 3: # Check limit before adding  current_node.product_indices.append(product_index)

3. Inserting Products Before Sorting

A critical mistake is building the Trie before sorting the products array. Since we're storing indices and want the lexicographically smallest products, the indices must correspond to the sorted array.

Incorrect Implementation:

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:  trie = Trie()   # Wrong: Building trie before sorting  for index, product in enumerate(products):  trie.insert(product, index)   products.sort() # Sorting after building trie breaks index mapping   suggestion_indices = trie.search(searchWord)  return [[products[index] for index in indices] for indices in suggestion_indices]

Correct Implementation:

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:  # Sort first to ensure indices correspond to lexicographic order  products.sort()   trie = Trie()  for index, product in enumerate(products):  trie.insert(product, index)   suggestion_indices = trie.search(searchWord)  return [[products[index] for index in indices] for indices in suggestion_indices]

These pitfalls can lead to runtime errors, incorrect results, or inefficient solutions. Always ensure proper null checking, enforce constraints (like the 3-product limit), and maintain correct index-to-product mapping by sorting before building the data structure.

Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Trie Introduction

Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie

Vanilla Binary Search

https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More